fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define all(ac) ac.begin(),ac.end()
  4. #define task "tet"
  5. #define fi first
  6. #define se second
  7. #define pii pair<int,int>
  8. #define db long double
  9. #define int long long
  10.  
  11. struct event {
  12.     int id, l, r, pos;
  13.     bool operator <(const event o) const {
  14.         if(id != o.id) return id < o.id;
  15.         if(r != o.r) return r < o.r;
  16.         return l < o.l;
  17.     }
  18. };
  19.  
  20. int32_t main() {
  21.     if(fopen(task".inp", "r")) {
  22.         freopen(task".inp","r",stdin);
  23.         freopen(task".out","w",stdout);
  24.     }
  25.  
  26.     ios::sync_with_stdio(false);
  27.     cin.tie(0), cout.tie(0);
  28.  
  29.     int n; cin >> n;
  30.     int a[n + 1];
  31.     for(int i=1;i<=n;i++) cin >> a[i];
  32.     int sz = sqrt(n);
  33.  
  34.     vector <int> id(n + 5, 0);
  35.     for(int i=1, cur = 1;i<=n;i++) {
  36.         id[i] = cur;
  37.         if(i == cur * sz) cur++;
  38.     }
  39.  
  40.     int Q; cin >> Q;
  41.     vector <event> qr;
  42.     for(int i=1;i<=Q;i++) {
  43.         int l, r; cin >> l >> r;
  44.         qr.push_back({id[l], l, r, i});
  45.     }
  46.  
  47.     sort(all(qr));
  48.  
  49.     vector <int> ans(Q + 1, 0);
  50.     int cur_r = -1, cur_l = -1;
  51.     int temp = -1;
  52.     map <int, int> cnt;
  53.     int cur_cnt = 0;
  54.     for(auto e : qr) {
  55.         if(e.id != temp) {
  56.             cnt.clear();
  57.             temp = e.id;
  58.             cur_r = e.l;
  59.             cur_l = e.l;
  60.             cnt[a[e.l]]++;
  61.             cur_cnt = 1;
  62.         }
  63.         while(cur_l < e.l) {
  64.             cnt[a[cur_l]]--;
  65.             if(cnt[a[cur_l]] == 0) cur_cnt--;
  66.             cur_l++;
  67.         }
  68.         while(cur_l > e.l) {
  69.             cur_l--;
  70.             cnt[a[cur_l]]++;
  71.             if(cnt[a[cur_l]] == 1) cur_cnt++;
  72.         }
  73.  
  74.         while(cur_r < e.r) {
  75.             cur_r++;
  76.             cnt[a[cur_r]]++;
  77.             if(cnt[a[cur_r]] == 1) cur_cnt++;
  78.         }
  79.  
  80.         ans[e.pos] = cur_cnt;
  81.     }
  82.  
  83.     for(int i=1;i<=Q;i++) cout << ans[i] << '\n';
  84.     return 0;
  85. }
Success #stdin #stdout 0.01s 5328KB
comments (?)
stdin 
5
1 1 2 1 3
3
1 5
2 4
3 5
stdout 
3
2
3
https://ideone.com/bgUK9e
language:
C++ (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!