fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define bint __int128
  7. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  8.  
  9. struct BIT {
  10.     int n;
  11.     vector<int> tree;
  12.  
  13.     void init(int _n) { n = _n, tree.assign(n, 0); }
  14.  
  15.     void add(int at, int value) {
  16.         for (int i = at + 1; i <= n; i += i & -i) {
  17.             tree[i - 1] += value;
  18.         }
  19.     }
  20.  
  21.     int sum(int exc) {
  22.         int ans = 0;
  23.         for (int i = exc; i > 0; i -= i & -i) {
  24.             ans += tree[i - 1];
  25.         }
  26.         return ans;
  27.     }
  28.  
  29.     int sum(int inc, int exc) {
  30.         return sum(exc) - sum(inc);
  31.     }
  32. };
  33.  
  34. void getShitDone() {
  35.     int y, n; cin >> y >> n;
  36.     vector<array<int, 2>> x(y);
  37.     for(int i = 0; i < y; i++){
  38.         cin >> x[i][0];
  39.         x[i][1] = i + 1;
  40.     }
  41.  
  42.     vector<array<int, 4>> v(n);
  43.     vector<int> ans(n, -1);
  44.     for(int i = 0; i < n; i++){
  45.         cin >> v[i][1] >> v[i][0] >> v[i][2];
  46.         v[i][3] = i;
  47.         if(v[i][0] <= x[v[i][1] - 1][0])
  48.             ans[i] = 0;
  49.     }
  50.  
  51.     sort(x.rbegin(), x.rend());
  52.     sort(v.rbegin(), v.rend());
  53.  
  54.     int cur = 0;
  55.     BIT tree; tree.init(y + 10);
  56.     for(int i = 0; i < n; i++){
  57.         int id = v[i][3], p = v[i][0], a = v[i][1], f = v[i][2];
  58.         while(cur < y && p <= x[cur][0]){
  59.             tree.add(x[cur][1], 1);
  60.             cur++;
  61.         }
  62.  
  63.         if(ans[id] != -1)
  64.             continue;
  65.  
  66.         ans[id] = tree.sum(a + 1, a + f + 1);
  67.     }
  68.  
  69.     for(auto it : ans)
  70.         cout << it << '\n';
  71.  
  72. }
  73.  
  74. signed main() {
  75.     _3bkarm
  76.  
  77.     int ts = 1;
  78. //    cin >> ts;
  79.     while (ts--) getShitDone();
  80.  
  81.     return 0;
  82. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/m6ZBbD
language:
C++ (gcc 8.3)
created:
3 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!