fork download
copy 
  1. /*
  2.   Warn - Don't change next line else you will get WA verdict. Online Judge is configured to give WA if next line is not present.
  3.   Author - Aryan Choudhary (@aryanc403)
  4.  
  5.   const short DEBUG { 0 };
  6.   #define debug(x) if (DEBUG) cout << #x << " = " << x << '\n'
  7. */
  8.  
  9. #pragma warning(disable:4996)
  10. #pragma comment(linker, "/stack:200000000")
  11. #pragma GCC optimize ("Ofast")
  12. #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
  13. #pragma GCC optimize ("-ffloat-store")
  14.  
  15. #include<iostream>
  16. #include<bits/stdc++.h>
  17. #include<stdio.h>
  18. using namespace std;
  19. #define fo(i,n)   for(i=0;i<(n);++i)
  20. #define repA(i,j,n)   for(i=(j);i<=(n);++i)
  21. #define repD(i,j,n)   for(i=(j);i>=(n);--i)
  22. #define pb push_back
  23. #define mp make_pair
  24. #define X first
  25. #define Y second
  26. #define endl "\n"
  27. #define PI 3.1415926535897932384626433832795
  28. typedef long long int lli;
  29. typedef long double mytype;
  30. typedef pair<lli,lli> ii;
  31. typedef vector<ii> vii;
  32. typedef vector<lli> vi;
  33.  
  34. //const lli [3] ={ 999119999L,1000000007L,1000992299L};
  35. //const lli [3] ={ 97L,101L,103L};
  36. //const lli  = chrono::high_resolution_clock::now().time_since_epoch().count();
  37. clock_t time_p=clock();
  38. void aryanc403()
  39. {
  40.     time_p=clock()-time_p;
  41.     cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
  42. }
  43.  
  44. class CMP
  45. {
  46. public:
  47.     bool operator()(lli a , lli b) //For min priority_queue .
  48.     {
  49.         return ! ( a <= b );
  50.     }
  51. };
  52.  
  53. void add( map<ii,lli> &m, ii x,lli cnt=1)
  54. {
  55.     map<ii,lli> ::iterator jt;
  56.     jt=m.find(x);
  57.     if(jt==m.end())         m.insert(mp(x,cnt));
  58.     else                    jt->Y+=cnt;
  59. }
  60.  
  61. void del( map<ii,lli> &m, ii x,lli cnt=1)
  62. {
  63.     map<ii,lli> ::iterator jt;
  64.     jt=m.find(x);
  65.     if(jt->Y<=cnt)            m.erase(jt);
  66.     else                      jt->Y-=cnt;
  67. }
  68.  
  69. bool cmp(const ii &a,const ii &b)
  70. {
  71.     return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
  72. }
  73. const lli INF = 0xFFFFFFFFFFFFFFFL;
  74. const lli mod = 1000000007L;
  75.  
  76.     lli T,n,i,j,k,in,cnt,l,r,x,y,val,lx,rx,ly,ry;
  77.     lli m;
  78.     // string s;
  79.     char s[5];
  80.     map<ii,lli> final;
  81.     map<ii,lli> a;
  82.     map<ii,lli> :: iterator it;
  83.     //priority_queue < lli , vector < lli > , CMP > pq;// min priority_queue .
  84.  
  85. void updateY(lli root,lli l,lli r,lli pos,lli val,lli x)
  86. {
  87.     if(l>r||r<pos||pos<l)
  88.         return;
  89.     add(final,{x,root},val);
  90.     if(l==r)
  91.         return;
  92.     lli m=(l+r)/2;
  93.     updateY(2*root,l,m,pos,val,x);
  94.     updateY(2*root+1,m+1,r,pos,val,x);
  95. }
  96.  
  97. void updateX(lli root,lli l,lli r,lli x,lli y,lli val)
  98. {
  99.     if(l>r||r<x||x<l)
  100.         return;
  101.     updateY(1,1,n,y,val,root);
  102.     if(l==r)
  103.         return;
  104.     lli m=(l+r)/2;
  105.     updateX(2*root,l,m,x,y,val);
  106.     updateX(2*root+1,m+1,r,x,y,val);
  107. }
  108.  
  109. void update(lli x,lli y,lli val)
  110. {
  111.     updateX(1,1,n,x,y,val);
  112. }
  113.  
  114. lli queryY(lli x,lli root,lli l,lli r,lli L,lli R)
  115. {
  116.     if(l>r||r<L||R<l)
  117.         return 0;
  118.     if(L<=l&&r<=R)
  119.     {
  120.         it=final.find({x,root});
  121.         if(it==final.end())
  122.             return 0;
  123.         return it->Y;
  124.     }
  125.     lli m=(l+r)/2;
  126.     return queryY(x,2*root,l,m,L,R)+queryY(x,2*root+1,m+1,r,L,R);
  127. }
  128.  
  129. lli queryX(lli root,lli l,lli r,lli L,lli R,lli yl,lli yr)
  130. {
  131.     if(l>r||r<L||R<l)
  132.         return 0;
  133.     if(L<=l&&r<=R)
  134.     {
  135.         return queryY(root,1,1,n,yl,yr);
  136.     }
  137.     lli m=(l+r)/2;
  138.     return queryX(2*root,l,m,L,R,yl,yr)+queryX(2*root+1,m+1,r,L,R,yl,yr);
  139. }
  140.  
  141. lli query(lli lx,lli ly,lli rx,lli ry)
  142. {
  143.     return queryX(1,1,n,lx,ly,rx,ry);
  144. }
  145.  
  146. int main(void) {
  147.     ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  148.     // freopen("txt.in", "r", stdin);
  149.     // freopen("txt.out", "w", stdout);
  150. // cout<<std::fixed<<std::setprecision(35);
  151. scanf(" %lld",&T);// cin>>T;
  152. while(T--)
  153. {
  154.     // cin>>n;
  155.     final.clear();
  156.     a.clear();
  157.     scanf(" %lld",&n);
  158.     // cin>>s;
  159.     scanf(" %s",s);
  160.     while(s[2]!='D')
  161.     {
  162.         if(s[2]=='T')
  163.         {
  164.             // cin>>x>>y>>val;
  165.             scanf(" %lld %lld %lld",&x,&y,&val);
  166.             x++;y++;
  167.             it=a.find({x,y});
  168.             if(it==a.end())
  169.             {
  170.                 a.insert(mp(mp(x,y),val));
  171.                 update(x,y,val);
  172.             }
  173.             else
  174.             {
  175.                 update(x,y,val-it->Y);
  176.                 it->Y=val;
  177.             }
  178.         }
  179.         else if(s[2]=='M')
  180.         {
  181.             // cin>>lx>>ly>>rx>>ry;
  182.             scanf(" %lld %lld %lld %lld",&lx,&ly,&rx,&ry);
  183.             lx++;ly++;rx++;ry++;
  184.             cout<<query(lx,rx,ly,ry)<<endl;
  185.         }
  186.         // cin>>s;
  187.         scanf(" %s",s);
  188.     }
  189. }   aryanc403();
  190.     return 0;
  191. }
Success #stdin #stdout #stderr 0s 15256KB
comments (?)
stdin
copy 
2
4
SET 0 0 1
SUM 0 0 3 3
SET 2 2 12
SUM 2 2 2 2
SUM 2 2 3 3
SUM 0 0 2 2
END
4
SET 0 0 1
SUM 0 0 3 3
SET 2 2 12
SUM 2 2 2 2
SUM 2 2 3 3
SUM 0 0 2 2
END
stdout
copy 
1
12
12
13
1
12
12
13
stderr
copy 
Time Taken : 6e-05
https://ideone.com/rbnsm8
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!