fork download
copy 
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <algorithm>
  4. #include <string.h>
  5. #include <stdbool.h>
  6. #include <math.h>
  7. #define ll long long int
  8. #define MAX (100000+10)     //////////////// change, added brackets :)
  9. #define ull unsigned long long int
  10. #define gcd(a,b)    __gcd(a,b)
  11.  
  12. using namespace std;
  13.  
  14. struct info
  15. {
  16.     int zero,one,two,lazy;
  17. } tree[MAX*5];
  18.  
  19. void update_lazy(int node)
  20. {
  21.     int temp = tree[node].zero;
  22.     tree[node].zero = tree[node].two;
  23.     tree[node].two = tree[node].one;
  24.     tree[node].one = temp;
  25. }
  26.  
  27. void update_node(int node,int left)
  28. {
  29.     tree[left].lazy +=  tree[node].lazy;
  30.     tree[left+1].lazy +=  tree[node].lazy;
  31.  
  32.     tree[node].lazy%=3;
  33.     int shift = tree[node].lazy;
  34.     while(shift--)
  35.     {
  36.         update_lazy(left);
  37.         update_lazy(left+1);
  38.     }
  39.     tree[node].lazy=0;
  40. }
  41.  
  42. void marge(int node, int left, int right)
  43. {
  44.     tree[node].zero= tree[left].zero + tree[right].zero;
  45.     tree[node].one= tree[left].one + tree[right].one;
  46.     tree[node].two= tree[left].two + tree[right].two;
  47. }
  48.  
  49. void build(int node, int b, int e)
  50. {
  51.     if (b == e)
  52.     {
  53.         tree[node].one = 0;
  54.         tree[node].two = 0;
  55.         tree[node].lazy = 0;
  56.         tree[node].zero = 1;
  57.  
  58.         return;
  59.     }
  60.     int Left = node * 2;
  61.     int Right = node * 2 + 1;
  62.     int mid = (b + e) / 2;
  63.     build(Left, b, mid);
  64.     build(Right, mid + 1, e);
  65.  
  66.     marge(node,Left,Right);
  67.  
  68. }
  69.  
  70. void update(int node, int l, int r, int i, int j)
  71. {
  72.     //cout<<node<<" "<<l<<" "<<r<<" "<<i<<" "<<j<<endl;
  73.     int Left = node*2;
  74.     if(tree[node].lazy!=0 && l != r){     //////////////// change, added condition l != r
  75.         update_node(node,Left);
  76.     }
  77.     //no overlap
  78.     if(l>r || l>j || r<i) return;
  79.  
  80.     //total overlap
  81.     if(l>=i && r<=j){
  82.         tree[node].lazy++;
  83.         update_lazy(node);
  84.         return;
  85.     }
  86.     //partial overlap
  87.     int mid = (l+r)/2;
  88.     update(Left,l,mid,i,j);
  89.     update(Left+1,mid+1,r,i,j);
  90.  
  91.     marge(node,Left,Left+1);
  92.  
  93. }
  94.  
  95. int query(int node,int l,int r,int i,int j) ///////////// change, some optimizations
  96. {
  97.     if(l>r || l>j || r<i) return 0;
  98.     if(tree[node].lazy!=0 && l != r){     //////////////// change, added condition l != r
  99.         update_node(node,node*2);
  100.     }
  101.  
  102.     if(l>=i && r<=j) return tree[node].zero;
  103.  
  104.     int mid = (l+r)/2;
  105.     int Left = node*2;
  106.  
  107.     if( j <= mid )
  108.     	return query(Left,l,mid,i,j);
  109. 	if(mid < i)
  110. 		return query(Left+1,mid+1,r,i,j);
  111.  
  112.     return query(Left,l,mid,i,j) + query(Left+1,mid+1,r,i,j);
  113. }
  114.  
  115. int main()
  116. {
  117.     int t,no=0;
  118.     //scanf("%d",&t);
  119.  
  120.     //while(t--)
  121.     {
  122.         int n,q,a;
  123.         scanf("%d %d",&n,&q);
  124.  
  125.         memset(tree,0,sizeof(tree));
  126.         build(1,1,n);
  127.  
  128.         //printf("Case %d:\n",++no);
  129.         while(q--)
  130.         {
  131.             int type,l,r;
  132.             scanf("%d %d %d",&type,&l,&r);
  133.             l++;
  134.             r++;
  135.  
  136.             if(type == 0)
  137.             {
  138.                 update(1,1,n,l,r);
  139.             }
  140.             else
  141.             {
  142.                 printf("%d\n",query(1,1,n,l,r));
  143.             }
  144.         }
  145.     }
  146.  
  147.     return 0;
  148. }
  149.  
Success #stdin #stdout 0s 11280KB
comments (?)
stdin
copy 
4 7
1 0 3
0 1 2
0 1 3
1 0 0
0 0 3
1 3 3
1 0 3
stdout
copy 
4
1
0
2
https://ideone.com/wNQAWh
language:
C++14 (gcc 8.3)
created:
7 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!