fork(1) download 
  1. #include<iostream>
  2. #include<stdio.h>
  3. using namespace std;
  4.  
  5. #define max 100001
  6.  
  7. inline void S(int &x) {
  8. register int c = getchar_unlocked();
  9. x = 0;
  10. int neg = 0;
  11. for(; ((c<48 || c>57) && c != '-'); c = getchar_unlocked());
  12. if(c=='-') {
  13.        neg = 1;
  14.         c = getchar_unlocked();
  15.     }
  16.     for(; c>47 && c<58 ; c = getchar_unlocked())
  17.     {
  18.         x = (x<<1) + (x<<3) + c - 48;
  19.     }
  20.     if(neg)
  21.         x = -x;
  22. }
  23.  
  24. struct rem{
  25. int r0,r1,r2;
  26. };
  27.  
  28. rem tree[3*max];
  29. int lazy[3*max]={0};
  30.  
  31. void prepare(int node)
  32. {
  33. lazy[node] = (lazy[node])%3;
  34. int ans=lazy[node],t;
  35. if(ans==1)
  36. {
  37. t= tree[2*node].r2;
  38. tree[2*node].r2= tree[2*node].r1;
  39. tree[2*node].r1= tree[2*node].r0;
  40. tree[2*node].r0= t;
  41.  
  42. t= tree[2*node+1].r2;
  43. tree[2*node+1].r2= tree[2*node+1].r1;
  44. tree[2*node+1].r1= tree[2*node+1].r0;
  45. tree[2*node+1].r0= t;
  46. }
  47. else if(ans==2)
  48. {
  49. t= tree[2*node].r2;
  50. tree[2*node].r2= tree[2*node].r0;
  51. tree[2*node].r0= tree[2*node].r1;
  52. tree[2*node].r1= t;
  53.  
  54. int t= tree[2*node+1].r2;
  55. tree[2*node+1].r2= tree[2*node+1].r0;
  56. tree[2*node+1].r0= tree[2*node+1].r1;
  57. tree[2*node+1].r1= t;
  58. }
  59.  
  60. else return;
  61.  
  62. lazy[2*node] = (lazy[2*node] + lazy[node])%3;
  63. lazy[2*node+1] = (lazy[2*node+1] + lazy[node])%3;
  64. lazy[node]=0;
  65. }
  66.  
  67. void make_tree(int node, int start, int end)
  68. {
  69. if(start==end)
  70. {
  71. tree[node].r0= 1;
  72. tree[node].r1= 0;
  73. tree[node].r2= 0;
  74. return;
  75. }
  76. int mid = (start+end)/2;
  77. make_tree(2*node, start, mid);
  78. make_tree(2*node+1, mid+1, end);
  79. tree[node].r0= (end-start+1);
  80. tree[node].r1= 0;
  81. tree[node].r2= 0;
  82. }
  83.  
  84. void update(int node, int start, int end, int ra1, int ra2)
  85. {
  86. if(ra1>end || ra2<start) return;
  87. if(start>=ra1 && end<=ra2)
  88.  {
  89.    int temp=tree[node].r2;
  90.    tree[node].r2= tree[node].r1;
  91.    tree[node].r1= tree[node].r0;
  92.    tree[node].r0= temp;
  93.    lazy[node]= (lazy[node]+1)%3;
  94.    return;
  95.  }
  96. int mid= (start+end)/2;
  97. if(lazy[node]) prepare(node);
  98. update(2*node, start, mid,ra1,ra2);
  99. update(2*node+1, mid+1, end, ra1, ra2);
  100. tree[node].r0= tree[2*node].r0 + tree[2*node+1].r0;
  101. tree[node].r1= tree[2*node].r1 + tree[2*node+1].r1;
  102. tree[node].r2= tree[2*node].r2 + tree[2*node+1].r2;
  103. }
  104.  
  105. int query(int node, int start, int end, int ra1, int ra2)
  106. {
  107. if(ra1>end || ra2<start)
  108.  return 0;
  109. if(start>=ra1 && end<=ra2)
  110.  return tree[node].r0;
  111. if(lazy[node]) prepare(node);
  112.  
  113. int mid = (start+end)/2;
  114. return query(2*node, start, mid, ra1, ra2) + query(2*node+1, mid+1,end,ra1,ra2);
  115. }
  116.  
  117. int main()
  118. {
  119. 	std::ios_base::sync_with_stdio(false);
  120. int q,n,a,f,x,y;
  121. //cin>>n>>q;
  122. S(n); S(q);
  123. make_tree(1,0,n-1);
  124. while(q--)
  125. {
  126. //cin>>f>>x>>y;
  127. S(f); S(x); S(y);
  128. if(f==0)
  129. update(1,0,n-1,x,y);
  130. else
  131. cout<<query(1,0,n-1,x,y)<<endl;
  132. }
  133. return 0;
  134. }
Success #stdin #stdout 0s 8172KB
comments (?)
stdin 
73 90
0 47 69
0 47 71
0 10 33
0 30 71
1 4 21
1 41 72
0 56 64
1 29 59
0 5 29
1 68 71
0 26 28
1 4 27
1 31 65
1 45 65
1 22 68
1 52 70
0 66 70
0 13 51
1 66 71
1 19 20
1 14 52
1 55 67
1 14 63
1 38 56
1 55 72
1 18 21
1 60 61
0 68 71
1 47 52
0 26 67
0 58 61
0 5 64
0 4 33
0 49 69
0 58 67
1 36 67
0 39 62
0 51 56
1 46 50
0 29 48
0 67 68
1 59 60
0 65 68
0 21 50
0 28 30
1 67 72
0 48 62
1 52 72
1 21 21
0 37 46
1 63 65
1 42 72
0 45 54
1 29 51
0 34 64
0 57 71
1 30 33
0 27 67
0 6 60
0 54 65
0 70 72
0 71 71
0 47 58
1 34 72
1 51 55
0 59 71
0 22 36
0 68 69
0 16 38
1 17 43
1 43 49
0 17 24
0 55 55
1 38 62
0 60 72
0 36 37
0 18 24
0 70 71
0 44 47
0 33 36
0 34 69
1 22 27
0 1 16
1 14 37
0 52 60
0 61 63
1 41 65
0 24 26
0 68 68
1 20 48
stdout 
6
24
9
2
3
10
10
16
9
1
2
18
2
21
4
4
4
0
1
11
0
0
4
9
1
0
10
7
1
18
2
8
4
11
2
7
5
12
https://ideone.com/Vpi5he
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

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!