fork(1) download
copy 
  1. /*
  2.     author: kartik8800
  3. */
  4. #include<bits/stdc++.h>
  5. #define ll long long
  6. #define pb push_back
  7. #define fr(a,b) for(ll i = a; i < b; i++)
  8. #define mod 1000000007
  9. #define inf (1LL<<60)
  10. #define all(x) (x).begin(), (x).end()
  11. #define prDouble(x) cout << fixed << setprecision(10) << x
  12. #define triplet pair<ll,pair<ll,ll>>
  13. #define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
  14. using namespace std;
  15. const int rootN = 555;
  16.  
  17. int freq[200000];
  18. int distinct;
  19. int ar[200000];
  20.  
  21. struct query
  22. {
  23.     int L;
  24.     int R;
  25.     int q_no;
  26.     int block_no;
  27.     bool operator < (query& q2)
  28.     {
  29.         if(block_no < q2.block_no)
  30.             return 1;
  31.         else if(block_no > q2.block_no)
  32.             return 0;
  33.         else return R < q2.R;
  34.     }
  35. };
  36.  
  37. void Add(int& elem)
  38. {
  39.     if(!freq[elem])distinct++;
  40.     freq[elem]++;
  41. }
  42. void Remove(int& elem)
  43. {
  44.     freq[elem]--;
  45.     if(!freq[elem])
  46.         distinct--;
  47. }
  48.  
  49. void adjust(int& curr_l, int& curr_r, query& q)
  50. {
  51.     while(curr_l > q.L)
  52.     {
  53.         curr_l--;
  54.         Add(ar[curr_l]);
  55.     }
  56.     while(curr_r < q.R)
  57.     {
  58.         curr_r++;
  59.         Add(ar[curr_r]);
  60.     }
  61. 	while(curr_l < q.L)
  62.     {
  63.         Remove(ar[curr_l]);
  64.         curr_l++;
  65.     }
  66.     while(curr_r > q.R)
  67.     {
  68.         Remove(ar[curr_r]);
  69.         curr_r--;
  70.     }
  71.  
  72. }
  73.  
  74. void solve(vector<query>& queries)
  75. {
  76.     vector<int> answer(queries.size());
  77.     sort(queries.begin(), queries.end());
  78.     memset(freq, 0, sizeof freq);
  79.     distinct = 1;
  80.  
  81.     int curr_l = queries[0].L;
  82.     int curr_r = queries[0].L;
  83.  
  84.     freq[ar[curr_l]]++;
  85.  
  86.     for(query& qr : queries)
  87.     {
  88.         adjust(curr_l, curr_r, qr);
  89.         answer[qr.q_no] = distinct;
  90.     }
  91.  
  92.     for(int x : answer)
  93.             cout<<x<<'\n';
  94. }
  95.  
  96. int main() {
  97.    fast_io;
  98.    int n,q;
  99.    cin >> n >> q;
  100.  
  101.    map<int,int> coordinateCompress;
  102.    int compressed_Num = 1;
  103.  
  104.    for(int i = 0; i < n; i++)
  105.    {
  106.        cin >> ar[i];
  107.        if(coordinateCompress.find(ar[i]) != coordinateCompress.end()){
  108.         ar[i] = coordinateCompress[ar[i]];
  109.        }
  110.        else{
  111.         coordinateCompress[ar[i]] = compressed_Num;
  112.         ar[i] = compressed_Num++;
  113.        }
  114.    }
  115.  
  116.    vector<query> queries(q);
  117.    for(int i = 0; i < q; i++)
  118.    {
  119.        int u,v;
  120.        cin >> u >>v;
  121.        queries[i].L = u-1;
  122.        queries[i].R = v-1;
  123.        queries[i].q_no = i;
  124.        queries[i].block_no = u/rootN;
  125.    }
  126.    solve(queries);
  127.    return 0;
  128. }
  129.  
Success #stdin #stdout 0s 4532KB
comments (?)
stdin
copy 
5 3
3 2 3 1 2
1 3
2 4
1 5
stdout
copy 
2
3
3
https://ideone.com/RkC547
language:
C++14 (gcc 8.3)
created:
4 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!