fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define MOD 1000000007
  3. using namespace std;
  4. typedef long long ll;
  5. typedef pair<ll, ll> ii;
  6. ll n, q, tp = 1;
  7. ii mang[30004];
  8. struct dl
  9. {
  10.     ll x;
  11.     ll y;
  12.     ll z;
  13.     ll id;
  14.     ll ans;
  15. };
  16. dl ques[30004];
  17. ll bit[30004];
  18. void update(ll i)
  19. {
  20.     for (; i <= n; i += i & -i)
  21.         bit[i]++;
  22. }
  23. ll get(ll i)
  24. {
  25.     ll s = 0;
  26.     for (; i > 0; i -= i & -i)
  27.         s += bit[i];
  28.     return s;
  29. }
  30. bool cmp1(ii s1, ii s2)
  31. {
  32.     return s1.first > s2.first;
  33. }
  34. bool cmp2(dl s1, dl s2)
  35. {
  36.     return s1.id < s2.id;
  37. }
  38. bool cmp3(dl s1, dl s2)
  39. {
  40.     return s1.z > s2.z;
  41. }
  42. int main()
  43. {
  44.     ios_base::sync_with_stdio(NULL);
  45.     cin.tie(0);
  46.     cout.tie(0);
  47.     cin >> n;
  48.     for (ll i = 1; i <= n; i++)
  49.     {
  50.         cin >> mang[i].first;
  51.         mang[i].second = i;
  52.     }
  53.     sort(mang + 1, mang + 1 + n, cmp1);
  54.     cin >> q;
  55.     for (ll i = 1; i <= q; i++)
  56.     {
  57.         cin >> ques[i].x >> ques[i].y >> ques[i].z;
  58.         ques[i].id = i;
  59.     }
  60.     sort(ques + 1, ques + 1 + q, cmp3);
  61.     for (ll i = 1; i <= q; i++)
  62.     {
  63.         // cout << ques[i].z;
  64.         while (tp <= n && mang[tp].first > ques[i].z)
  65.         {
  66.             update(mang[tp].second);
  67.             tp++;
  68.             // cout << tp;
  69.         }
  70.         ques[i].ans = get(ques[i].y) - get(ques[i].x - 1);
  71.     }
  72.     sort(ques + 1, ques + 1 + q, cmp2);
  73.     for (ll i = 1; i <= q; i++)
  74.         cout << ques[i].ans << '\n';
  75. }
  76.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Zn1SjW
problem KQUERY, based on SPOJ submission 35630301 (CPP14), 2026-03-23 02:32:31
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!