fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define fast ios::sync_with_stdio(false);cin.tie(0)
  4. #define pb push_back
  5. #define digit(x) floor(log10(x))+1
  6. #define mod 1000000007
  7. typedef long long ll;
  8. typedef long double ld;
  9. typedef vector<vector<ll>> matrix;
  10. typedef vector<ll> arr;
  11. typedef vector<string> vs;
  12. typedef vector<pair<ll,ll>> pv;
  13. #define in1(x) scanf("%lld",&x)
  14. #define in2(x,y) scanf("%lld %lld",&x,&y)
  15. #define in3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
  16. #define all(x) x.begin(),x.end()
  17. #define debug(x) cerr << #x << " is " << x << endl;
  18. ll bit[2000000]={0};
  19. struct Point{
  20.     ll x,y,z;
  21. };
  22. void update(int i,ll val,ll n){
  23.     ll s=bit[i];
  24.     while(i<=n){
  25.         bit[i]+=val-s;
  26.         i+=(i&(-i));
  27.     }
  28. }
  29. ll query(ll x){
  30.     ll ans=0;
  31.     while(x>0){
  32.         ans+=bit[x];
  33.         x-=(x&(-x));
  34.     }
  35.     return ans;
  36. }
  37. int main(){
  38.     fast;
  39.     ll t;
  40.     cin>>t;
  41.     while(t--){
  42.         ll n,q;
  43.         memset(bit,0,sizeof(bit));
  44.         cin>>n>>q;
  45.         ll q1=q;
  46.         set<tuple<ll,ll,ll>>al;
  47.         vector<pair<tuple<ll,ll,ll>,ll>>xq;
  48.         map<tuple<ll,ll,ll>,ll>m;
  49.         ll countx=1;
  50.         vector<pair<tuple<ll,ll,ll>,tuple<ll,ll,ll>>>qu;
  51.         vector<bool>h;
  52.         while(q--){
  53.             string s;
  54.             cin>>s;
  55.             if(s=="UPDATE"){
  56.                 ll w,x,y,z;
  57.                 h.pb(1);
  58.                 cin>>x>>y>>z>>w;
  59.                 al.insert(make_tuple(x,y,z));
  60.                 xq.push_back(make_pair(make_tuple(x,y,z),w));
  61.             }else{
  62.                 ll x1,x2,y1,y2,z1,z2;
  63.                 h.pb(0);
  64.                 cin>>x1>>y1>>z1>>x2>>y2>>z2;
  65.                 al.insert(make_tuple(x1,y1,z1));
  66.                 al.insert(make_tuple(x2,y2,z2));
  67.                 qu.push_back(make_pair(make_tuple(x1,y1,z1),make_tuple(x2,y2,z2)));
  68.             }
  69.         }
  70.         for(auto i : al){
  71.             m[i]=countx++;
  72.         }
  73.         ll i=0,j=0,p=0;
  74.         while(q1--){
  75.             if(h[i]==1){
  76.                 tuple<ll,ll,ll>o=xq[j].first;
  77.                 update(m[o],xq[j].second,countx);
  78.                 j++;
  79.             }else{
  80.                 cout<<query(m[qu[p].second])-query(m[qu[p].first]-1)<<endl;
  81.                 p++;
  82.             }
  83.             i++;
  84.         }
  85.     }
  86.     return 0;
  87. }
Success #stdin #stdout 0s 4520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ovOmVa
language:
C++14 (gcc 8.3)
created:
5 years 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!