fork download
copy 
  1. // ROOT : DRAGON3012009 : WA in Real Life
  2. #include <bits/stdc++.h>
  3. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  4. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  5. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  6. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  7. #define ll long long
  8. #define el "\n"
  9. #define fi first
  10. #define se second
  11. #define _ROOT_ int main()
  12. #define M 1000000007
  13. #define MAXN 1000001
  14. #define INF (1ll<<30)
  15. #define BLOCK 425
  16. #define NAME "file"
  17. #define debug(a) cout << #a << " = " << a << endl;
  18. using namespace std;
  19.  
  20. ll n, m, q ;
  21. ll a[MAXN] ;
  22. ll res[MAXN ] ;
  23. ll mp[MAXN ] ;
  24. vector<ll> pos[MAXN ] ;
  25. vector<ll> cpr ;
  26. vector<pair<ll,ll> > que[MAXN ] ;
  27. vector<ll> big ;
  28.  
  29. struct Seg {
  30.     ll val[MAXN << 2 ] ;
  31.     void update(ll id, ll l, ll r, ll pos, ll value ) {
  32.         if(l == r ) val[id] = max(val[id], value ) ;
  33.         else {
  34.             ll m = l + r >> 1 ;
  35.             if(m >= pos ) update(id << 1, l, m, pos, value ) ;
  36.             else update(id << 1 | 1, m + 1, r, pos, value ) ;
  37.             val[id] = max(val[id << 1], val[id << 1 | 1 ]) ;
  38.         }
  39.     }
  40.  
  41.     ll get(ll id, ll l, ll r, ll u, ll v ) {
  42.         if(u > r || v < l ) return 0 ;
  43.         if(u <= l && v >= r ) return val[id] ;
  44.         ll m = l + r >> 1 ;
  45.         return max(get(id << 1, l, m,u, v ), get(id << 1 | 1, m + 1, r, u, v )) ;
  46.     }
  47. } seg ;
  48.  
  49.  
  50. void init() {
  51.     cin >> n >> q ;
  52.     FOR(i, 1, n ) cin >> a[i] ;
  53.     FOR(i, 1, n ) cpr.push_back(a[i]) ;
  54.     compare(cpr) ;
  55.     FOR(i, 1, n ) a[i] = lower_bound(cpr.begin(), cpr.end(), a[i] ) - cpr.begin() + 1 ;
  56.     FOR(cnt, 1, q ) {
  57.         ll l, r ;
  58.         cin >> l >> r ;
  59.         que[l].push_back({r, cnt } ) ;
  60.     }
  61. }
  62.  
  63. void solve() {
  64.     FORD(i, n, 1 ) {
  65.         pos[a[i]].push_back(i) ;
  66.         if(pos[a[i]].size() < BLOCK  ) {
  67.         for(ll v : pos[a[i]] ) seg.update(1 , 0 , n , v , v - i ) ;
  68.         }else if(!mp[a[i]]&& pos[a[i]].size() >= BLOCK)
  69.         {
  70.         mp[a[i]] = true ;
  71.         big.push_back(a[i]);
  72.         }
  73.         for(auto [r , id ] : que[i] ) {
  74.             ll ans = seg.get(1 , 0 , n , i , r ) ;
  75.             for(ll v : big ) {
  76.                 auto it = upper_bound(pos[i].begin() , pos[i].end() , r ) ;
  77.                 if(it == pos[i].begin() ) continue ;
  78.                 ans = max(ans , abs( *prev(it) - pos[i][0] ) ) ;
  79.             }
  80.             res[id] = ans ;
  81.         }
  82.     }
  83.     FOR(i , 1 , q ) cout << res[i] << el ;
  84. }
  85.  
  86. _ROOT_ {
  87.     // freopen(NAME".inp" , "r" , stdin);
  88.     // freopen(NAME".out" , "w", stdout) ;
  89.     ios_base::sync_with_stdio(0);
  90.     cin.tie(0);
  91.     cout.tie(0);
  92.     int t = 1; // cin >> t ;
  93.     while(t--) {
  94.         init();
  95.         solve();
  96.     }
  97.     return (0&0);
  98. }
  99.  
Success #stdin #stdout 0.01s 52808KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/0mvBlE
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!