fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Query {
  6.     int l, r, val;
  7.     int ans;
  8. };
  9.  
  10. const int maxn = 30010;
  11. const int maxq = 200010;
  12. int n, q;
  13. pair<int, int> a[maxn];
  14. Query qr[maxq];
  15.  
  16. vector<int> val_it[maxn * 2];
  17. vector<Query*> qr_it[maxn * 2];
  18.  
  19. int main() {
  20. #ifdef LOCAL
  21.     freopen("main.inp", "r", stdin);
  22.     freopen("main.out", "w", stdout);
  23. #endif
  24.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  25.     cin >> n;
  26.     for (int i = 0; i < n; ++i) {
  27.         cin >> a[i].first;
  28.         a[i].second = i;
  29.     }
  30.  
  31.     cin >> q;
  32.     vector<Query*> temp_qr;
  33.     for (int i = 0; i < q; ++i) {
  34.         cin >> qr[i].l >> qr[i].r >> qr[i].val;
  35.         --qr[i].l;
  36.         qr[i].ans = 0;
  37.         temp_qr.push_back(qr + i);
  38.     }
  39.  
  40.     sort(a, a + n, greater<>());
  41.     sort(temp_qr.begin(), temp_qr.end(), [](const Query* u, const Query* v) { return u->val > v->val; });
  42.  
  43.     for (int i = 0; i < n; ++i) {
  44.         for (int p = a[i].second + n; p > 0; p >>= 1)
  45.             val_it[p].push_back(a[i].first);
  46.     }
  47.  
  48.     for (auto cur_qr: temp_qr) {
  49.         for (int l = cur_qr->l + n, r = cur_qr->r + n; l < r; l >>= 1, r >>= 1) {
  50.             if (l & 1) qr_it[l++].push_back(cur_qr);
  51.             if (r & 1) qr_it[--r].push_back(cur_qr);
  52.         }
  53.     }
  54.  
  55.     for (int root = 1; root < 2 * n; ++root) {
  56.         auto& vi = val_it[root];
  57.         auto& qi = qr_it[root];
  58.         if (vi.empty() or qi.empty()) continue;
  59.         int ptr_v = 0;
  60.         for (auto cur_qr: qi) {
  61.             while (ptr_v < (int)vi.size() and vi[ptr_v] > cur_qr->val) ++ ptr_v;
  62.             cur_qr->ans += ptr_v;
  63.         }
  64.     }
  65.  
  66.     for (int i = 0; i < q; ++i) cout << qr[i].ans << '\n';
  67.  
  68.     return 0;
  69. }
  70.  
Success #stdin #stdout 0s 6504KB
comments (?)
stdin
copy 
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2
stdout
copy 
2
0
3
https://ideone.com/R9GWOS
language:
C++ (gcc 8.3)
created:
3 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!