fork download
copy 
  1. // Author : zvwgvx
  2. // Problem : 
  3.  
  4. #pragma GCC optimize("O3,unroll-loops")
  5. #include <bits/stdc++.h>
  6.  
  7. #if LOCAL
  8. #include "algo/debug.h"
  9. #endif
  10.  
  11. using namespace std;
  12. using ll = long long;
  13.  
  14. const int MOD = 1e9 + 7;
  15. const int LIMIT = 1e6 + 7;
  16. const ll INF = LLONG_MAX;
  17.  
  18. int block, cnt = 0;
  19. vector<int> arr;
  20. vector<int> freq(LIMIT, 0);
  21.  
  22. struct query {
  23.     int l, r, idx;
  24. };
  25.  
  26. bool compare(const query& a, const query& b) {
  27.     int b_a = a.l / block, b_b = b.l / block;
  28.     if (b_a != b_b) return b_a < b_b;
  29.     return (b_a & 1) ? (a.r > b.r) : (a.r < b.r);
  30. }
  31.  
  32. void add(int pos) {
  33.     if (freq[arr[pos]] == 0) ++cnt;
  34.     ++freq[arr[pos]];
  35. }
  36.  
  37. void remove(int pos) {
  38.     --freq[arr[pos]];
  39.     if (freq[arr[pos]] == 0) --cnt;
  40. }
  41.  
  42. signed main() { 
  43.     cin.tie(nullptr), cout.tie(nullptr) -> ios_base::sync_with_stdio(false);
  44.  
  45.     #define task "sol"
  46.     if (fopen(task".inp", "r")) {
  47.         freopen(task".inp", "r", stdin), freopen(task".out", "w", stdout);
  48.     }
  49.  
  50.     int n;
  51.     cin >> n;
  52.  
  53.     block = sqrt(n);
  54.  
  55.     arr.resize(n);
  56.     for (int& val : arr) cin >> val;
  57.  
  58.     vector<int> comp = arr;
  59.     sort(comp.begin(), comp.end());
  60.     comp.erase(unique(comp.begin(), comp.end()), comp.end());
  61.  
  62.     for (int& val : arr) val = lower_bound(comp.begin(), comp.end(), val) - comp.begin();
  63.  
  64.     int q;
  65.     cin >> q;
  66.  
  67.     vector<query> queries(q);
  68.     vector<int> result(q);
  69.  
  70.     for (int i = 0; i < q; ++i) {
  71.         cin >> queries[i].l >> queries[i].r;
  72.         --queries[i].l, --queries[i].r;
  73.         queries[i].idx = i;
  74.     }
  75.  
  76.     sort(queries.begin(), queries.end(), compare);
  77.  
  78.     int l = 0, r = -1;
  79.     for (auto [L, R, P] : queries) {
  80.         while (l > L) add(--l);
  81.         while (r < R) add(++r);
  82.         while (l < L) remove(l++);
  83.         while (r > R) remove(r++);
  84.  
  85.         result[P] = cnt;
  86.     }
  87.  
  88.     for (int i = 0; i < q; ++i) cout << result[i] << '\n';
  89.  
  90.     return 0;
  91. }
Success #stdin #stdout 0.01s 7320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/cF1afZ
language:
C++14 (clang 8.0)
created:
2 days 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!