fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ii pair <int, int>
  3. #define vi vector <int>
  4. #define vvi vector <vi>
  5. #define vvvi vector <vvi>
  6. #define ld long double
  7. #define ll long long
  8. #define pb push_back
  9. #define BIT(mask,i) (((mask) >> (i)) & 1ll)
  10. #define MASK(i) (1ll << i)
  11. #define ONBIT(mask,i) (mask | (1ll << (i)))
  12. #define OFFBIT(mask, i) (mask &~ (1ll << (i)))
  13. #define FOR(i,a,b) for (int i=a;i<=b;i++)
  14. #define FORD(i,a,b) for (int i=a;i>=b;i--)
  15. #define FORV(v,h) for (auto v:h)
  16. using namespace std;
  17. const int MOD = 1e9 + 7;
  18. const int MAXN = 2e5 + 105;
  19. const long long oo = 1e18 + 7;
  20. int n, q;
  21. int ans[MAXN];
  22. int st[4 * MAXN];
  23.  
  24. struct ZATA {
  25.     int val, id;
  26. } a[MAXN];
  27.  
  28. struct DATA {
  29.     int l, r, k, id;
  30. } ques[MAXN];
  31.  
  32. bool cmp1(ZATA A, ZATA B) {
  33.     return A.val > B.val;
  34. }
  35.  
  36. bool cmp2(DATA A, DATA B) {
  37.     return A.k > B.k;
  38. }
  39.  
  40. void upd(int id, int l, int r, int u, int v) {
  41.     if (l > v || r < u) return;
  42.     if (l >= u && r <= v) {
  43.         st[id] = 1;
  44.         return;
  45.     }
  46.     int mid = (l + r) / 2;
  47.     upd(id * 2, l, mid, u, v);
  48.     upd(id * 2 + 1, mid + 1, r, u, v);
  49.     st[id] = st[id * 2] + st[id * 2 + 1];
  50. }
  51.  
  52. int get(int id, int l, int r, int u, int v) {
  53.     if (l > v || r < u) return 0;
  54.     if (l >= u && r <= v) return st[id];
  55.     int mid = (l + r) / 2;
  56.     return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
  57. }
  58.  
  59. main() {
  60.     ios_base::sync_with_stdio(false);
  61.     cin.tie(0);cout.tie(0);
  62.     cin >> n;
  63.     FOR(i,1,n) {
  64.         cin >> a[i].val;
  65.         a[i].id = i;
  66.     }
  67.     cin >> q;
  68.     FOR(i,1,q) {
  69.         cin >> ques[i].l >> ques[i].r >> ques[i].k;
  70.         ques[i].id = i;
  71.     }
  72.  
  73.     sort(a + 1, a + n + 1, cmp1);
  74.     sort(ques + 1, ques + q + 1, cmp2);
  75.     int j = 1;
  76.     FOR(i,1,q) {
  77.         while (a[j].val > ques[i].k && j <= n) {
  78.             upd(1, 1, n, a[j].id, a[j].id);
  79.             j++;
  80.         }
  81.         ans[ques[i].id] = get(1, 1, n, ques[i].l, ques[i].r);
  82.     }
  83.  
  84.     FOR(i,1,q) cout << ans[i] << '\n';
  85.  
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/oHyLmI
language:
C++14 (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!