fork download
copy 
  1. #include <unordered_set>
  2. #include <unordered_map>
  3. #include <bits/stdc++.h>
  4.  
  5. #define lli long long int
  6. #define all(x) x.begin(),x.end()
  7. #define b(x) x.begin()
  8. #define e(x) x.end()
  9. #define sz(x) x.size()
  10. #define vi vector<int>
  11. #define vli vector<long long int>
  12. #define pi pair<int,int>
  13. #define pli pair<long long int,long long int>
  14. #define pr pair
  15. #define ff first
  16. #define ss second
  17. #define vt vector
  18. #define um unordered_map
  19. #define us unordered_set
  20. #define mod 1000000007
  21. #define pb push_back
  22. #define pf push_front
  23. #define endl '\n'
  24. #define loop(i,a,b) for(lli i=a;i<b;i++)
  25. #define loopr(i,a,b) for(lli i=a;i>=b;i--)
  26. #define foit(it,x)   for(auto &it:x)
  27.  
  28. using namespace std;
  29.  
  30. int dx[] = {-1,1,0,0,-1,-1,1,1};
  31. int dy[] = {0,0,1,-1,-1,1,-1,1};
  32.  
  33. const int block = 200;
  34.  
  35. typedef struct
  36. {
  37.     int l;
  38.     int r;
  39.     int id;
  40. }query;
  41.  
  42. bool cmp(query &a, query &b)
  43. {
  44.     return (((a.l/block)<(b.l/block))||(a.r<=b.r));
  45. }
  46.  
  47. void add(auto &m, int num)
  48. {
  49.     m[num]++;
  50. }
  51.  
  52. void removee(auto &m, int num)
  53. {
  54.     if(m.find(num)!=e(m))
  55.     {
  56.         m[num]--;
  57.         if(m[num]==0) m.erase(num);
  58.     }
  59. }
  60. void solve()
  61. {
  62.     int t=1;
  63.     //cin>>t;
  64.     while(t--)
  65.     {
  66.         int n; cin>>n;
  67.         vi v(n);
  68.         loop(i,0,n) cin>>v[i];
  69.         int q; cin>>q;
  70.         vt<query>Q;
  71.         loop(i,0,q)
  72.         {
  73.             int l,r; cin>>l>>r; l--,r--;
  74.             Q.pb({l,r,(int)i});
  75.         }
  76.         sort(all(Q),cmp);
  77.         int curr_l = Q[0].l,curr_r = Q[0].r;
  78.         vi ans(q);
  79.         map<int,lli>m;
  80.         loop(i,curr_l,curr_r+1) m[v[i]]++;
  81.         loop(i,0,q)
  82.         {
  83.             while(Q[i].l<curr_l)
  84.             {
  85.                 curr_l--;
  86.                 add(m,v[curr_l]);
  87.             }
  88.             while(Q[i].r>curr_r)
  89.             {
  90.                 curr_r++;
  91.                 add(m,v[curr_r]);
  92.             }
  93.             while(Q[i].l>curr_l)
  94.             {
  95.                 removee(m,v[curr_l]);
  96.                 curr_l++;
  97.             }
  98.             while(Q[i].r<curr_r)
  99.             {
  100.                 removee(m,v[curr_r]);
  101.                 curr_r--;
  102.             }
  103.             ans[Q[i].id] = sz(m);
  104.         }
  105.         loop(i,0,q) cout<<ans[i]<<endl;
  106.     }
  107. }
  108.  
  109.  
  110. int main()
  111. {
  112.     clock_t start, end;
  113.     start = clock();
  114.     ios_base::sync_with_stdio(false);
  115.     cin.tie(NULL);
  116.     cout.tie(NULL);
  117.     #ifndef ONLINE_JUDGE
  118.     freopen("input.txt","r",stdin);
  119.     freopen("output.txt","w",stdout);
  120.     #endif
  121.     solve();
  122.     end = clock();
  123.     #ifndef ONLINE_JUDGE
  124.     double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
  125.     cout << "Time taken is : " << fixed
  126.          << time_taken << setprecision(5);
  127.     cout << " sec " << endl;
  128.     #endif
  129.     return 0;
  130. }
  131.  
Runtime error #stdin #stdout 0s 5648KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/glcbor
problem DQUERY, based on SPOJ submission 28062617 (CPP14), 2021-06-15 17:02:25
language:
C++14 (gcc 8.3)
created:
2 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!