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<];
  36. int kroot[MAXN];
  37. int root[MAXN];
  38. int lt[MAXN];
  39. int rt[MAXN];
  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. int res[MAXN];
  80. tuple<int,int,int,int> queries[MAXN];
  81.  
  82. int main()
  83. {
  84.     scanf("%d", &n);
  85.     next_free = 1;
  86.     kroot[n] = INF;
  87.     root[n] = next_free++;
  88.     build(1,1,n);
  89.     FOR(i, 1, n) {
  90.         scanf("%d", &t);
  91.         v.pb(mp(t, i));
  92.     }
  93.     sort(ALL(v));
  94.     FORD(i, n-1, 0) {
  95.         kroot[i] = v[i].st;
  96.         root[i] = insert(root[i+1], v[i].nd, 1, n);
  97.     }
  98.     scanf("%d", &qr);
  99.     REP(i, 0, qr) {
  100.         scanf("%d%d%d", &a, &b, &c);
  101.         queries[i] = make_tuple(c, a, b, i);
  102.     }
  103.     sort(queries, queries+qr);
  104.     int j = n;
  105.     FORD(i, qr-1, 0) {
  106.         while(j && kroot[j-1] > get<0>(queries[i])) j--;
  107.         res[get<3>(queries[i])] = query(root[j], get<1>(queries[i]), get<2>(queries[i]), 1, n);
  108.     }
  109.     REP(i, 0, qr) printf("%d\n", res[i]);
  110.     return 0;
  111. }
  112.  
  113.  
  114.  
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/j0N7lB
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!