fork download
copy 
  1. // FOR COMPETITIVE PROGRAMMING
  2. /*
  3.     _____________      ________
  4.    |             |    /        |
  5.    |____     ____|   /    _____|
  6.         |    |      /    /
  7.         |    |     |    |
  8.         |    |     |    |
  9.         |    |     |    |
  10.   __    |    |     |    |
  11.  \  \___/    /     |     \_____
  12.   \         /       \          |
  13.    \_______/         \_________|
  14.  
  15.  
  16.  
  17. Murder, drugs, cash, and greed
  18. It touches everyone and everything
  19. Within the walls there's no escaping the disease
  20. Sidewalks turn to pharmacies
  21. All the pimps and pushers territories
  22. Dollars pouring in from the victims trapped within
  23. Schoolyard's a place of sorrow
  24. Pray your children live to see tomorrow
  25. A place where mothers cry, and kiss their dying sons goodbye
  26. Living in a state of fear
  27. Afraid of everything they see or hear
  28. Someone they love may get shot
  29. For drugs they never even bought!
  30.  
  31. Violence is a way of life
  32. Revenge delivered with a gun or knife
  33. Paybacks are a bitch
  34. They'll leave you dying in a ditch
  35. Caught in the hypnotic spell
  36. Their life's story they'll never life to tell
  37. In a hazy curtain, they can't see the end is certain
  38. Imprisoned by narcotic chains
  39. Life for some will never be the same
  40. Trapped in walls of glass
  41. Hoping that this all will pass
  42. But some will find their way outside
  43. Face the evil, eyes open wide
  44. Break the bonds that pull you in
  45. Escape the hell that thrives...
  46.  
  47. Within the walls
  48. Of chaos and despair
  49. Most are unemployed
  50. Living on welfare
  51. Prowling the halls
  52. The vultures come to feed
  53. On the flesh of those
  54. Who are enslaved to the need
  55. The final curtain falls
  56. And no one sheds a fear
  57. Their pleas for help always seem to fall
  58. Upon deaf ears
  59. Within the walls of chaos they forgot
  60. That dignity and sanity
  61. Are things that can't be bought
  62.  
  63. With every passing day
  64. Another life is cast astray
  65. Wear the wrong colors
  66. And you might get blown away
  67.  
  68. Turn of a page
  69. Another name's crossed off the list
  70. Shot between the eyes
  71. With a rig clenched in his fist
  72.  
  73. Driven to the grave
  74. Ruled by need for kicks
  75. Extract their own gold teeth
  76. To satisfy their fix
  77.  
  78. There's cracks in the foundation
  79. The time will soon arrive
  80. When the walls will crumble down
  81. And bury everyone alive!
  82.  
  83. Within the walls...
  84. Within the walls of chaos...
  85. Within the walls...
  86. Within the walls of chaos...
  87. Within the walls...
  88. Within the walls of chaos!
  89. */
  90.  
  91. #include<bits/stdc++.h>
  92. using namespace std;
  93.  
  94. #define run if(1)cout<<__LINE__<<endl;
  95. #define Clear( a, b ) memset( a, b, sizeof( a ) )
  96.  
  97. #define swapp(v) swap(v[0],v[v.size()-1])
  98.  
  99. #define vvi vector<vector< int> >
  100. #define vi vector<int>
  101. #define ff first
  102. #define ss second
  103. #define no cout<<"NO"<<endl;
  104. #define yes cout<<"YES"<<endl;
  105.  
  106. #define rep(i,n) for(int i=0;i<n;i++)
  107. #define REP(i,j,n,k) for(int i=j;i<n;i+=k)
  108. #define mp make_pair
  109. #define pb push_back
  110. #define pii  pair<int,int>
  111. #define piii pair<int,pair<int,int> >
  112. #define piiii pair<pair<int,int>,pair<int,int> >
  113. #define ll long long
  114.  
  115. #define llinf 1000000000000000000
  116. #define inf 1000050000
  117. #define MOD 1000000007
  118. #define abs llabs
  119. #define BOOST ios::sync_with_stdio(false);  cin.tie(NULL); cout.tie(NULL);
  120.  
  121. inline long long  max3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
  122. inline long long  min3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
  123. //########################################################//
  124. // for modinverse calculation  // here MOD = 10^9+7
  125. ll extgcd(ll a, ll b, ll &x, ll &y) {                     // ExtGCD
  126.     if (b == 0) {
  127.         x = 1;
  128.         y = 0;
  129.         return a;
  130.     }
  131.     ll d = extgcd(b, a%b, y, x);
  132.     y -= a / b * x;
  133.     return d;
  134. }
  135.  
  136. inline ll mod(ll a, ll m) {                               // mod a wrt b
  137.     return (a % m + m) % m;
  138. }
  139.  
  140. ll modinv(ll a) {                                         // mod inverse a wrt 10^9+7
  141.     ll x, y;
  142.     extgcd(a, MOD, x, y);
  143.     return mod(x, MOD);
  144. }
  145. //#########################################################//
  146. // GCD
  147. ll gcd(ll u, ll v) {
  148.   ll r;
  149.   while (0 != v) {
  150.     r = u % v; u = v; v = r;
  151.   }
  152.   return u;
  153. }
  154. //###########################################################//
  155. // LCM
  156. ll lcm(ll u, ll v) {
  157.   return u/gcd(u,v)*v;
  158. }
  159. //##########################################################//
  160. //void floyd_warshall(ll n){
  161. //  rep(i,n)rep(j,n)rep(k,n)d[j][k]=min(d[j][k],d[j][i]+d[i][k]);
  162. //}
  163. //##########################################################//
  164. // Get all factors  // cnt in 'a' array
  165. void get_all_factors(int a[],ll int n){
  166.     ll int w=sqrt(n);
  167.     for(int i=1;i<=w;i++){
  168.         if(n%i==0){  a[i]++;   a[n/i]++;  }   }
  169.     ll int x=ceil(sqrt(n)); if(sqrt(n)==ceil(sqrt(n)))  a[(int)sqrt(n)]--;
  170. }
  171. //#################################//
  172. // COMPUTE nCr
  173. ll int memo[100000][110]={0};
  174. ll C(ll n, ll r)
  175. {
  176.     if(r==0 || r==n)
  177.         return 1;
  178.     if(memo[n][r] != -1) return memo[n][r];
  179.     return memo[n][r] = ( C(n-1, r-1) % MOD + C(n-1, r) % MOD ) % MOD;
  180. }
  181. //##########################################################//
  182.  
  183. // Dont use these variables------> mod,lcm,gcd,MOD,forn,mp,pb,modinv
  184.  
  185. // Usable shortcuts
  186. // ff->first , ss->second , abs->>llabs , MOD , forn(j,n) , mp , pb , pii ,
  187. // inf->10^9+5^5 ,
  188.  
  189. // functns:-->fast(a,n) a^n , gcd(u,v) , lcm(u,v) , mod(a,m) wrt m, modinv(a) wrt MOD, get_all_factors(a[],n) , Clear (a[],b) set all ai to val b,
  190. //            ---------       --------   --------   -------         ---------          ---------------------    -------------
  191. //###########################################//
  192. // Debugging
  193. int valid(string s, int i){ if(s=="lol" or i==-inf){   return 0;  }  return 1; }
  194. void status(string s1="lol",ll int i1=-inf,string s2="lol",ll int i2=-inf,string s3="lol",ll int i3=-inf){
  195. if(1){
  196. if(valid(s1,i1)){  cout<<s1<<"="<<i1<<"  ";  }
  197. if(valid(s2,i2)){  cout<<s2<<"="<<i2<<"  ";  }
  198. if(valid(s3,i3)){  cout<<s3<<"="<<i3<<"  ";  }
  199. cout<<endl;
  200. }  }
  201.  
  202. //###########################################//
  203. // Compute power with or without MOD
  204.  
  205. ll int poww(ll b,ll e){if(e==0)return 1;else if(e%2==0){ll a=pow(b,e/2);return a*a;}else {ll a=pow(b,e/2);return b*a*a;}}
  206. ll int powm(ll x,ll y,ll m=MOD){x=x%m;ll res=1;while(y){if(y&1)res=res*x;res%=m;y=y>>1;x=x*x;x%=m;}return res;}
  207. //###########################################//
  208.  
  209. //## Segment Tree Reference
  210. //
  211. // build() function
  212. // update() function
  213. // lazy() function
  214. // query() function
  215.  
  216. //###########################################//
  217.  
  218. // min and max segment tree in one code only
  219.  
  220. int c[1000000]={0};
  221. int lazy[10000000]={0};
  222. int mintree[10000000]={0};
  223. int maxtree[10000000]={0};
  224.  
  225. void lazyprop(int index,int s,int e)
  226. {
  227. //    cout<<"lazy"<<endl;
  228.     mintree[index]+=lazy[index];
  229.     maxtree[index]+=lazy[index];
  230.     if(s<e)    // s!=e
  231.     {
  232.         int left=2*index;
  233.         int right=2*index+1;
  234.         lazy[left]+=lazy[index];
  235.         lazy[right]+=lazy[index];
  236.         lazy[index]=0;             // most important part
  237.     }
  238.     return;
  239. }
  240.  
  241. void build(int s,int e, int index)
  242. {
  243. //    cout<<"index="<<index<<endl;
  244.     if(s>e)
  245.     {
  246.         return ;
  247.     }
  248.     if(s==e)
  249.     {
  250.      mintree[index]=c[s];
  251.      maxtree[index]=c[s];
  252.      return;
  253.     }
  254.     int mid=(s+e)>>1;
  255.     build(s,mid,2*index);
  256.     build(mid+1,e,2*index+1);
  257.     maxtree[index]=max(maxtree[2*index],maxtree[2*index+1]);
  258.     mintree[index]=min(mintree[2*index],mintree[2*index+1]);
  259.     return ;
  260. }
  261.  
  262. void updaterange(int s,int e,int l,int r,int val,int index)
  263. {
  264.     lazyprop(index,s,e);
  265.  
  266.    // cout<<"updating "<<s<<" "<<e<<endl;
  267.  
  268.     if(l<=s and e<=r)
  269.     {
  270.         //lazy[index]=val;
  271.         lazy[index]+=val;
  272.         lazyprop(index,s,e);         // this lies completely in range,
  273.         return ;
  274.     }
  275.  
  276.     if(s>r or e<l or s>e)    // missed s>e case
  277.     {
  278.         return ;
  279.     }
  280.  
  281.     int mid=(s+e)>>1;
  282.     updaterange(s,mid,l,r,val,2*index);
  283.     updaterange(mid+1,e,l,r,val,2*index+1);
  284.     maxtree[index]=max(maxtree[2*index],maxtree[2*index+1]);
  285.     mintree[index]=min(mintree[2*index],mintree[2*index+1]);
  286.     return ;
  287. }
  288.  
  289. int querymax(int s,int e,int l,int r,int index)
  290. {
  291.     lazyprop(index,s,e);
  292.  
  293.     if(e<l or s>r or s>e)    // missed s>e case
  294.     {
  295.         return -inf;  // out of range
  296.     }
  297.  
  298.     if(s>=l and e<=r)
  299.     {
  300.         return maxtree[index];
  301.     }
  302.  
  303.     int mid=(s+e)>>1;
  304.  
  305.     int lans=querymax(s,mid,l,r,2*index);
  306.     int rans=querymax(mid+1,e,l,r,2*index+1);
  307.  
  308.     return max(lans,rans);
  309. }
  310.  
  311. int querymin(int s,int e,int l,int r,int index)
  312. {
  313.     lazyprop(index,s,e);
  314.  
  315.     if(e<l or s>r or s>e)     // missed s>e case
  316.     {
  317.         return +inf;  // out of range
  318.     }
  319.  
  320.     if(s>=l and e<=r)
  321.     {
  322.         return mintree[index];
  323.     }
  324.  
  325.     int mid=(s+e)>>1;
  326.  
  327.     int lans=querymin(s,mid,l,r,2*index);
  328.     int rans=querymin(mid+1,e,l,r,2*index+1);
  329.  
  330.     return min(lans,rans);
  331. }
  332.  
  333. int main()
  334. {
  335.     BOOST
  336.  
  337.     int t;
  338.     cin>>t;
  339.  
  340.     while(t--)
  341.     {
  342.  
  343.   int n,q;
  344.   cin>>n>>q;
  345.  
  346.   int a[n+1]={0};
  347.  
  348.   REP(i,1,n+1,1)
  349.   {
  350.       int a[i];
  351.       cin>>a[i];
  352.       c[i]=c[i-1]+a[i];
  353.       cout<<i<<" "<<c[i]<<endl;
  354.   }
  355.  
  356.   build(1,n,1);
  357.  
  358.   while(q--)
  359.   {
  360.       char c;
  361.       cin>>c;
  362.       if(c=='Q')
  363.       {
  364.           int l,r;
  365.           cin>>l>>r;
  366.  
  367.             int cr=querymax(1,n,r,n,1);
  368.             int cl=querymin(1,n,1,l-1,1);
  369.            // cout<<cr<<" "<<cl<<" ans= ";
  370.             int ans=cr-cl;
  371.             cout<<"ans=";
  372.             cout<<ans<<endl;
  373.       }
  374.       else
  375.       {
  376.             int x,v;
  377.             cin>>x>>v;
  378.             updaterange(1,n,x,n,x-a[x],1); // made mistake in range to be updated   // made mistake in update value , wrote just x there
  379.             a[x]=v;
  380.       }
  381.   }
  382.  
  383.     }
  384. }
  385. //////////////////////////////////////////////
  386.  
Success #stdin #stdout 0s 4332KB
comments (?)
stdin
copy 
1
5 5
-1 2 -2 1 -3
Q 3 5
Q 2 4
U 1 1
Q 2 4
Q 3 5
stdout
copy 
1 -1
2 1
3 -1
4 0
5 -3
ans=-2
ans=1
ans=1
ans=-2
https://ideone.com/535uh0
language:
C++14 (gcc 8.3)
created:
4 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!