fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ALL(v) v.begin(), v.end()
  4. #define REP(i, a, b) for(int i = a; i < b; i++)
  5. #define REPD(i, a, b) for(int i = a; i > b; i--)
  6. #define REPLL(i, a, b) for(ll i = a; i < b; i++)
  7. #define FOR(i, a, b) for(int i = a; i <= b; i++)
  8. #define FORD(i, a, b) for(int i = a; i >= b; i--)
  9. #define FORLL(i, a, b) for(ll i = a; i <= b; i++)
  10. #define INF 2000000001
  11.  
  12. using namespace std;
  13.  
  14. typedef long long ll;
  15. typedef long double ld;
  16.  
  17. typedef pair<int, int> pii;
  18. typedef pair<ld, ld> pld;
  19. typedef vector<int>::iterator vit;
  20. typedef set<int>::iterator sit;
  21. typedef map<int, int>::iterator mit;
  22. typedef vector<int> vi;
  23. typedef vector<pii > vpii;
  24.  
  25. #define pb push_back
  26. #define mp make_pair
  27. #define st first
  28. #define nd second
  29.  
  30. #define EPS 1e-9
  31. #define PI acos(-1.0)
  32. #define MAXN 200007
  33.  
  34. int z, n, t, a, b, c;
  35. int ans[MAXN<<4];
  36. int kroot[MAXN];
  37. int root[MAXN];
  38. int lt[MAXN<<4];
  39. int rt[MAXN<<4];
  40. int next_free;
  41.  
  42. void build(int v, int l, int r) {
  43.     if(l==r) return;
  44.     lt[v] = next_free++;
  45.     rt[v] = next_free++;
  46.     int mid = (l+r)/2;
  47.     build(lt[v], l, mid);
  48.     build(rt[v], mid+1, r);
  49. }
  50.  
  51. int insert(int v, int x, int l, int r) {
  52.     int nv = next_free++;
  53.     if(l == r) {
  54.         ans[nv] = 1;
  55.         return nv;
  56.     }
  57.     int mid = (l+r)/2;
  58.     lt[nv] = lt[v];
  59.     rt[nv] = rt[v];
  60.     if(x <= mid) lt[nv] = insert(lt[v], x, l, mid);
  61.     else rt[nv] = insert(rt[v], x, mid+1, r);
  62.     ans[nv] = ans[lt[nv]] + ans[rt[nv]];
  63.     return nv;
  64. }
  65.  
  66. int query(int v, int x, int y, int l, int r) {
  67.     if(l>=x && r<=y) {
  68.         return ans[v];
  69.     }
  70.     int mid = (l+r)/2;
  71.     int ret = 0;
  72.     if(x <= mid) ret += query(lt[v], x, y, l, mid);
  73.     if(y>mid) ret += query(rt[v], x, y, mid+1, r);
  74.     return ret;
  75. }
  76.  
  77. vpii v;
  78. int qr;
  79.  
  80. int main()
  81. {
  82.     scanf("%d", &n);
  83.     next_free = 1;
  84.     kroot[n] = INF;
  85.     root[n] = next_free++;
  86.     build(1,1,n);
  87.     FOR(i, 1, n) {
  88.         scanf("%d", &t);
  89.         v.pb(mp(t, i));
  90.     }
  91.     sort(ALL(v));
  92.     FORD(i, n-1, 0) {
  93.         kroot[i] = v[i].st;
  94.         root[i] = insert(root[i+1], v[i].nd, 1, n);
  95.     }
  96.     scanf("%d", &qr);
  97.     REP(i, 0, qr) {
  98.         scanf("%d%d%d", &a, &b, &c);
  99.         int it = lower_bound(kroot, kroot+n+1, c+1)-kroot;
  100.         printf("%d\n", query(root[it], a, b, 1, n));
  101.     }
  102.     return 0;
  103. }
  104.  
  105.  
  106.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:1:25: fatal error: bits/stdc++.h: No such file or directory
 #include <bits/stdc++.h>
                         ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/OC64oc
language:
C (gcc 8.3)
created:
9 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!