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 build(ll arr[] , ll node , ll left , ll right)
  13. {
  14.     if(left == right)
  15.     {
  16.         tree[node] = arr[left];
  17.         return ;
  18.     }
  19.     ll mid = (left + right) >> 1 ;
  20.     build(arr,2*node , left , mid);
  21.     build(arr,2*node+1,mid+1,right);
  22.     tree[node] = tree[2*node] + tree[2*node+1];
  23. }
  24.  
  25. void update(ll node , ll left , ll right , ll from , ll to , ll val)
  26. {
  27.     if(lazy[node] != 0)
  28.     {
  29.         tree[node] += (right-left+1) * lazy[node];
  30.         if (left != right)
  31.         {
  32.             lazy[2*node] += lazy[node];
  33.             lazy[2*node+1] += lazy[node];
  34.         }
  35.         lazy[node] = 0;
  36.     }
  37.  
  38.     if (left > right || left > to || right < from)
  39.         return ;
  40.  
  41.     if(left >= from && right <= to)
  42.     {
  43.         tree[node] += (right-left+1)*val;
  44.  
  45.         if(left != right)
  46.         {
  47.             lazy[2*node] += val ;
  48.             lazy[2*node+1] += val ;
  49.         }
  50.         return ;
  51.     }
  52.     ll mid = (left + right) >> 1 ;
  53.     update(node*2 , left , mid , from , to , val);
  54.     update(2*node+1,mid+1,right,from,to,val);
  55.     tree[node] = tree[2*node] + tree[2*node+1];
  56. }
  57.  
  58. ll query(ll node , ll left, ll right, ll from, ll to)
  59. {
  60.     if(lazy[node] != 0)
  61.     {
  62.         tree[node] += (right - left + 1) * lazy[node];
  63.         if(left != right)
  64.         {
  65.             lazy[2*node] += lazy[node];
  66.             lazy[2*node+1] += lazy[node];
  67.         }
  68.         lazy[node] = 0 ;
  69.     }
  70.     if(left > right || left > to || right < from)
  71.         return 0 ;
  72.  
  73.     if(left >= from && right <= to)
  74.         return tree[node];
  75.  
  76.     ll mid = (left + right) >> 1 ;
  77.     return query(2*node , left , mid , from , to) +
  78.            query(2*node+1,mid+1,right,from,to);
  79. }
  80.  
  81. int main()
  82. {
  83.     ll t ;
  84.     cin>>t ;
  85.     ll cnt = 0;
  86.     while(t--)
  87.     {
  88.         ll n , q ;
  89.         cin>>n>>q ;
  90.         ll arr[100005] = {0};
  91.         build(arr,1,0,n-1);
  92.         cout<<"Scenario #"<<++cnt<<":\n";
  93.         while(q--)
  94.         {
  95.             string s; ;
  96.             ll x ,y ;
  97.             cin>>s>>x>>y;
  98.             if(x > y)
  99.                 cout<<"0\n";
  100.             else if(s[0] == 'a')
  101.                cout<<query(1,0,n-1,x-1,y-1)<<"\n";
  102.             else
  103.             {
  104.                 update(1,0,n-1,x-1,y-1,1);
  105.                 cout<<"OK\n";
  106.             }
  107.         }
  108.     }
  109.      return 0 ;
  110. }
  111.  
Success #stdin #stdout 0s 4456KB
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/Td4sDM
language:
C++ (gcc 8.3)
created:
6 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!