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
  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){
  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)
  96. {
  97.     if(l>r || l>j || r<i) return 0;
  98.     if(tree[node].lazy!=0){
  99.  
  100.     	update_node(node,node*2);
  101.     }
  102.     if(l>=i && r<=j) return tree[node].zero;
  103.     int mid = (l+r)/2;
  104.     int Left = node*2;
  105.     return query(Left,l,mid,i,j) + query(Left+1,mid+1,r,i,j);
  106. }
  107.  
  108. int main()
  109. {
  110.     int t,no=0;
  111.     // scanf("%d",&t);
  112.  
  113.     // while(t--)
  114.     {
  115.         int n,q,a;
  116.         scanf("%d %d",&n,&q);
  117.  
  118.         memset(tree,0,sizeof(tree));
  119.         build(1,1,n);
  120.  
  121.         printf("Case %d:\n",++no);
  122.         while(q--)
  123.         {
  124.             int type,l,r;
  125.             scanf("%d %d %d",&type,&l,&r);
  126.             l++;
  127.             r++;
  128.  
  129.             if(type == 0)
  130.             {
  131.                 update(1,1,n,l,r);
  132.             }
  133.             else
  134.             {
  135.                 printf("%d\n",query(1,1,n,l,r));
  136.             }
  137.         }
  138.     }
  139.  
  140.     return 0;
  141. }
  142.  
Success #stdin #stdout 0s 5020KB
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 
Case 1:
4
1
0
2
https://ideone.com/uV5pc4
language:
C++14 (gcc 8.3)
created:
8 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!