fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  4. #define ll long long
  5. #define pii pair<int, int>
  6. #define ppiii pair<pair<int, int>, int>
  7. #define pipii pair<int, pair<int, int>>
  8.  
  9. const int INF = 1e9;
  10. const int MOD = 1e9+7;
  11. const int N = 3e4+5;
  12.  
  13. struct query{
  14.     int l, r, k, id;
  15. } Q[200005];
  16. pii a[N];
  17. int seg[4*N];
  18. int n, q;
  19. int ans[200005];
  20.  
  21. void update(int id, int l, int r, int pos, int k){
  22.     if (l>pos || r<pos) return;
  23.     if (l==r){
  24.         seg[id] = 1;
  25.         return;
  26.     }
  27.     int m = (l+r)/2;
  28.     update(2*id, l, m, pos, k);
  29.     update(2*id+1, m+1, r, pos, k);
  30.     seg[id] = seg[2*id]+seg[2*id+1];
  31. }
  32.  
  33. int get(int id, int l, int r, int u, int v){
  34.     if (l>v || r<u){
  35.         return 0;
  36.     }
  37.     if (u<=l && r<=v){
  38.         return seg[id];
  39.     }
  40.     int m = (l+r)/2;
  41.     return get(2*id, l, m, u, v) + get(2*id+1, m+1, r, u, v);
  42. }
  43.  
  44. bool cmp_a(pii x, pii y){
  45.     return x.first > y.first;
  46. }
  47.  
  48. bool cmp_Q(query x, query y){
  49.     return x.k > y.k;
  50. }
  51.  
  52. int main(){
  53.     fastIO;
  54.  
  55.     cin >> n;
  56.     for (int i=1; i<=n; i++){
  57.         cin >> a[i].first;
  58.         a[i].second = i;
  59.     }
  60.     sort(a+1, a+1+n, cmp_a);
  61.     cin >> q;
  62.     for (int i=1; i<=q; i++){
  63.         cin >> Q[i].l >> Q[i].r >> Q[i].k;
  64.         Q[i].id = i;
  65.     }
  66.     sort(Q+1, Q+1+q, cmp_Q);
  67.     int j = 1;
  68.     for (int i = 1; i<=q; i++){
  69.         while (j<=n && a[j].first>Q[i].k){
  70.             update(1, 1, n, a[j].second, 1);
  71.             j++;
  72.         }
  73.         ans[Q[i].id] = get(1, 1, n, Q[i].l, Q[i].r);
  74.     }
  75.     for (int i=1; i<=q; i++){
  76.         cout << ans[i] << '\n';
  77.     }
  78.     return 0;
  79. }
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/QEXK6O
language:
C++14 (gcc 8.3)
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!