fork download 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. /*#include<ext/pb_ds/assoc_container.hpp>
  4. #include<ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. /*template <typename T>
  7. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  8. */typedef long long ll;
  9. typedef long double ld;
  10. typedef pair<ll,ll> pl;
  11. typedef pair<int,int> pii;
  12.  
  13. #define LOCAL 0
  14. #define dbg(x) cerr << #x << " is " << x << " "
  15. #define gll(x) scanf("%lld",&x)
  16. #define gll2(x,y) scanf("%lld%lld",&x,&y)
  17. #define gll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&y)
  18. #define gllarr(arr,n) f(i,n) gll(arr[i]);
  19. #define sz(x) ((int)x.size())
  20. #define s(x) sort(x.begin(),x.end())
  21. #define all(v) v.begin(),v.end()
  22. #define rs(v) { s(v) ; r(v) ; }
  23. #define r(v) {reverse(all(v));}
  24. #define pb push_back
  25. #define mp make_pair
  26. #define F first
  27. #define S second
  28. #define f(i,n) for(int i=0;i<n;i++)
  29. #define fr(i,n) for(int i=n-1;i>=0;i--)
  30. #define rep(i,a,b) for(int i=a;i<=b;i++)
  31. #define repr(i,a,b) for(int i=a;i>=b;i--)
  32.  
  33. const ll mod = 1000000007;
  34. const ll inf = (ll)1e16;
  35. const ld eps = 1e-12;
  36. const ll N = (int)1e5+55;
  37. const ll LOGN = 19;
  38. const ld PI = 3.14159265358979323846;
  39. ll mul(ll a, ll b, ll m = mod) { return (ll)(a * b) % m;}
  40. ll add(ll a, ll b, ll m = mod) { a += b; if(a >= m) a -= m; if(a < 0) a += m; return a;}
  41. ll power(ll a, ll b, ll m = mod) { if(b == 0) return 1; if(b == 1) return (a % m); ll x = power(a, b / 2, m); x = mul(x, x, m); if(b % 2) x = mul(x, a, m); return x;}
  42.  
  43. int n,m,q;
  44. int a[N];
  45. pair<pair<int,int>,int> queries[N];
  46. int blocksize;
  47. set<int> freq[N];
  48. int segtree[4*N];
  49. int answers[N];
  50.  
  51. void update(int node,int start,int end,int val,int idx)
  52. {
  53.     if(start == end)
  54.     {
  55.         segtree[node] = val;
  56.         return;
  57.     }
  58.     int mid = (start+end)>>1;
  59.     int lc = 2*node + 1;
  60.     int rc = lc + 1;
  61.     if(idx>=start && idx<=mid)
  62.         update(lc,start,mid,val,idx);
  63.     else
  64.         update(rc,mid+1,end,val,idx);
  65.     segtree[node] = max(segtree[lc],segtree[rc]);
  66. }
  67.  
  68. int query(int node,int start,int end,int qs,int qe)
  69. {
  70.     if(end<start || end<qs || start>qs)
  71.     {
  72.         return -1;
  73.     }
  74.     if(qs<=start && qe>=end)
  75.         return segtree[node];
  76.     int mid = (start+end)>>1;
  77.     int lc = 2*node + 1;
  78.     int rc = lc + 1;
  79.     return max(query(lc,start,mid,qs,qe),query(rc,mid+1,end,qs,qe));
  80. }
  81.  
  82. bool comp(pair<pair<int,int>,int>& a, pair<pair<int,int>,int>& b)
  83. {
  84.     int a1 = a.first.first/blocksize;
  85.     int a2 = a.first.second;
  86.     int b1 = b.first.first/blocksize;
  87.     int b2 = b.first.second;
  88.     return a1!=b1 ? a1 < b1 : a2 < b2;
  89. }
  90.  
  91. inline void add(int val,int idx)
  92. {
  93.     freq[val].insert(idx);
  94.     int to = 0;
  95.     if(freq[val].size()>1)
  96.     {
  97.         //int last = freq[val].size();
  98.         //to = freq[val][0] - freq[val][last-1];
  99.         to = *freq[val].rbegin() - *freq[val].begin();
  100.     }
  101.     update(0,0,N-1,to,val);
  102. }
  103.  
  104. inline void remove(int val,int idx)
  105. {
  106.     freq[val].erase(idx);
  107.     int to = 0;
  108.     if(freq[val].size()>1)
  109.     {
  110.         //int last = freq[val].size();
  111.         //to = freq[val][0] - freq[val][last-1];
  112.         to = *freq[val].rbegin() - *freq[val].begin();
  113.     }
  114.     update(0,0,N-1,to,val);
  115. }
  116.  
  117. int main()
  118. {
  119.     ios_base::sync_with_stdio(false);
  120.     cin.tie(NULL);
  121.     if(LOCAL)
  122.     {
  123.         freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\input.txt","r",stdin);
  124.         freopen("C:\\Users\\Dishant\\Desktop\\Collection-DEV c++\\output.txt","w",stdout);
  125.     }
  126.     cin>>n>>m>>q;
  127.     blocksize = static_cast<int>(sqrt(n));
  128.     f(i,n)
  129.         cin>>a[i];
  130.     f(i,q)
  131.     {
  132.         cin>>queries[i].first.first>>queries[i].first.second;
  133.         queries[i].second = i;
  134.     }
  135.     sort(queries,queries+q,comp);
  136.     int lptr = 0;
  137.     int rptr = -1;
  138.     f(i,q)
  139.     {
  140.         int l = queries[i].first.first - 1;
  141.         int r = queries[i].first.second - 1;
  142.         while(lptr < l)
  143.         {
  144.             remove(a[lptr],lptr);
  145.             lptr++;
  146.         }
  147.         while(rptr < r)
  148.         {
  149.             rptr++;
  150.             add(a[rptr],rptr);
  151.         }
  152.         while(lptr > l)
  153.         {
  154.             lptr--;
  155.             add(a[lptr],lptr);
  156.         }
  157.         while(rptr > r)
  158.         {
  159.             remove(a[rptr],rptr);
  160.             rptr--;
  161.         }
  162.         //cout<<queries[i].second<<" "<<segtree[0]<<endl;
  163.         answers[queries[i].second] = query(0,0,N-1,0,m);
  164.     }
  165.     f(i,q)
  166.         cout<<answers[i]<<"\n";
  167.     return 0;
  168. }
Success #stdin #stdout 0s 7852KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/9R37OL
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

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!