fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll ;
  6.  
  7.  
  8. const ll MAX = 100009 ;
  9. ll tree[5*MAX] = {0};
  10. ll lazy[5*MAX] = {0};
  11.  
  12. void update(ll node , ll left , ll right , ll from , ll to , ll val)
  13. {
  14.     if(lazy[node] != 0)
  15.     {
  16.         tree[node] += (right-left+1) * lazy[node];
  17.         if (left != right)
  18.         {
  19.             lazy[2*node] += lazy[node];
  20.             lazy[2*node+1] += lazy[node];
  21.         }
  22.         lazy[node] = 0;
  23.     }
  24.  
  25.     if (left > right || left > to || right < from)
  26.         return ;
  27.  
  28.     if(left >= from && right <= to)
  29.     {
  30.         tree[node] += (right-left+1)*val;
  31.  
  32.         if(left != right)
  33.         {
  34.             lazy[2*node] += val ;
  35.             lazy[2*node+1] += val ;
  36.         }
  37.         return ;
  38.     }
  39.     ll mid = (left + right) >> 1 ;
  40.     update(node*2 , left , mid , from , to , val);
  41.     update(2*node+1,mid+1,right,from,to,val);
  42.     tree[node] = tree[2*node] + tree[2*node+1];
  43. }
  44.  
  45. ll query(ll node , ll left, ll right, ll from, ll to)
  46. {
  47.     if(lazy[node] != 0)
  48.     {
  49.         tree[node] += (right - left + 1) * lazy[node];
  50.         if(left != right)
  51.         {
  52.             lazy[2*node] += lazy[node];
  53.             lazy[2*node+1] += lazy[node];
  54.         }
  55.         lazy[node] = 0 ;
  56.     }
  57.     if(left > right || left > to || right < from)
  58.         return 0 ;
  59.  
  60.     if(left >= from && right <= to)
  61.         return tree[node];
  62.  
  63.     ll mid = (left + right) >> 1 ;
  64.     return query(2*node , left , mid , from , to) +
  65.            query(2*node+1,mid+1,right,from,to);
  66. }
  67.  
  68. int main()
  69. {
  70.     ll t ;
  71.     scanf("%lld" , &t);
  72.     ll cnt = 0;
  73.     while(t--)
  74.     {
  75.         for(int i = 0 ; i < 5*MAX ; ++i)
  76.             lazy[0] = tree[0] = 0 ;
  77.         ll n , q ;
  78.         scanf("%lld %lld" , &n , &q);
  79.         ll arr[100005] = {0};
  80.         cout<<"Scenario #"<<++cnt<<":\n";
  81.         while(q--)
  82.         {
  83.             string s; ;
  84.             ll x ,y ;
  85.             cin>>s>>x>>y;
  86.             if(x > y)
  87.                 cout<<"0\n";
  88.             else if(s[0] == 'a')
  89.                cout<<query(1,0,n-1,x-1,y-1)<<"\n";
  90.             else
  91.             {
  92.                 update(1,0,n-1,x-1,y-1,1);
  93.                 cout<<"OK\n";
  94.             }
  95.         }
  96.     }
  97.      return 0 ;
  98. }
  99.  
Success #stdin #stdout 0s 4368KB
comments (?)
stdin
copy 
2
4 4
answer 1 4
modification 1 2
modification 2 3
answer 2 2
8 6
modification 2 4
modification 4 8
modification 4 5
answer 8 8 
modification 5 7
answer 4 8
stdout
copy 
Scenario #1:
0
OK
OK
2
Scenario #2:
OK
OK
OK
1
OK
11
https://ideone.com/NTrbFX
language:
C++ (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!