fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define endl "\n"
  4. #define mii map<int,int>
  5. #define mll map<ll,ll>
  6. #define pii pair<int,int>
  7. #define pll pair<ll,ll>
  8. #define fi first
  9. #define se second
  10. using namespace std;
  11. int n, q;
  12. pii a[100005];
  13. ll st[400005];
  14. struct query {
  15.     int ind, l, r, x;
  16. } b[100005];
  17. vector<pll> ans;
  18. bool cmp(query a, query b) {
  19.     return a.x>b.x;
  20. }
  21. void upd(int id, int l, int r, int pos, int val) {
  22.     if (l>pos || r<pos) return;
  23.     if (l==r) {
  24.         st[id]=val;
  25.         return;
  26.     }
  27.     int mid=(l+r)/2;
  28.     upd(id*2,l,mid,pos,val);
  29.     upd(id*2+1,mid+1,r,pos,val);
  30.     st[id]=st[id*2]+st[id*2+1];
  31. }
  32. ll gsum(int id, int l, int r, int u, int v) {
  33.     if (l>v || r<u) return 0;
  34.     if (l>=u && r<=v) return st[id];
  35.     int mid=(l+r)/2;
  36.     return gsum(id*2,l,mid,u,v)+gsum(id*2+1,mid+1,r,u,v);
  37. }
  38. int main() {
  39.     ios_base::sync_with_stdio(false);
  40.     cin.tie(0); cout.tie(0);
  41.     cin>>n>>q;
  42.     for (int i=1; i<=n; i++) {
  43.         cin>>a[i].fi;
  44.         a[i].se=i;
  45.     }
  46.     sort(a+1,a+n+1,greater<pii>());
  47.     for (int i=1; i<=q; i++) {
  48.         b[i].ind=i;
  49.         cin>>b[i].l>>b[i].r>>b[i].x;
  50.     }
  51.     sort(b+1,b+q+1,cmp);
  52.     int j=1;
  53.     for (int i=1; i<=q; i++) {
  54.         int l=b[i].l, r=b[i].r, x=b[i].x;
  55.         while (j<=n && a[j].fi>=x) {
  56.             upd(1,1,n,a[j].se,a[j].fi);
  57.             j++;
  58.         }
  59.         ans.push_back({b[i].ind,gsum(1,1,n,l,r)});
  60.     }
  61.     sort(ans.begin(),ans.end());
  62.     for (auto [i,j] : ans) {
  63.         cout<<j<<" ";
  64.     }
  65.     return 0;
  66. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/HHuZe5
language:
C++ (gcc 8.3)
created:
98 days 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!