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