fork download
copy 
  1. // God be praised
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int N = 1e5 + 5;
  6. struct node {
  7. 	int freq[9], i, lazy;
  8.  
  9. 	node () {
  10. 		fill(freq, freq + 9, 0);
  11. 		i = lazy = 0;
  12. 	}
  13. } tree[4*N];
  14.  
  15. void build (int idx, int nl, int nr) {
  16. 	tree[idx].freq[1] = (nr - nl) + 1;
  17.  
  18. 	if (nl == nr) return;
  19.  
  20. 	int mid = (nl + nr) / 2;
  21. 	build(idx*2+1, nl, mid);
  22. 	build(idx*2+2, mid+1, nr);
  23. }
  24.  
  25. void update (node &p, node &child) {
  26. 	int j = 0;
  27. 	for (int i = child.i; i < 9; i++, j++) {
  28. 		p.freq[j] += child.freq[i];
  29. 	}
  30. 	for (int i = 0; i < child.i; i++, j++) {
  31. 		p.freq[j] += child.freq[i];
  32. 	}
  33. }
  34.  
  35. void update (int idx) {
  36. 	node &p = tree[idx];
  37. 	fill(p.freq, p.freq + 9, 0);
  38. 	p.i = 0;
  39.  
  40. 	update(p, tree[idx*2+1]);
  41. 	update(p, tree[idx*2+2]);
  42. }
  43.  
  44. void add (int &a, int b) {
  45. 	a += b;
  46. 	if (a >= 9) {
  47. 		a -= 9;
  48. 	}
  49. }
  50.  
  51. void dec (int &a, int b) {
  52. 	a -= b;
  53. 	if (a < 0) {
  54. 		a += 9;
  55. 	}
  56. }
  57.  
  58. void propagate (int idx, int nl, int nr) {
  59. 	node &p = tree[idx];
  60.  
  61. 	if (p.lazy && (nl < nr)) {
  62. 		node &l = tree[idx*2+1];
  63. 		add(l.lazy, p.lazy);
  64. 		dec(l.i, p.lazy);
  65.  
  66. 		node &r = tree[idx*2+2];
  67. 		add(r.lazy, p.lazy);
  68. 		dec(r.i, p.lazy);
  69.  
  70. 		p.lazy = 0;
  71. 	}
  72. }
  73.  
  74. int fquery[9];
  75. void query (int idx, int nl, int nr, int ql, int qr) {
  76. 	if (nl > qr || ql > nr) return;
  77.  
  78. 	node &p = tree[idx];
  79.  
  80. 	if (nl >= ql && nr <= qr) {
  81. 		int j = 0;
  82. 		for (int i = p.i; i < 9; i++, j++) {
  83. 			fquery[j] += p.freq[i];
  84. 		}
  85. 		for (int i = 0; i < p.i; i++, j++) {
  86. 			fquery[j] += p.freq[i];
  87. 		}
  88. 		return;
  89. 	}
  90.  
  91. 	propagate(idx, nl, nr);
  92.  
  93. 	int mid = (nl + nr) / 2;
  94. 	query(idx*2+1, nl, mid, ql, qr);
  95. 	query(idx*2+2, mid+1, nr, ql, qr);
  96. }
  97.  
  98. void chord (int idx, int nl, int nr, int ql, int qr, int note) {
  99. 	if (nl > qr || ql > nr) return;
  100.  
  101. 	if (nl >= ql && nr <= qr) {
  102. 		node &p = tree[idx];
  103. 		add(p.lazy, note);
  104. 		dec(p.i, note);
  105. 		return;
  106. 	}
  107.  
  108. 	propagate(idx, nl, nr);
  109.  
  110. 	int mid = (nl + nr) / 2;
  111. 	chord(idx*2+1, nl, mid, ql, qr, note);
  112. 	chord(idx*2+2, mid+1, nr, ql, qr, note);
  113.  
  114. 	update(idx);
  115. }
  116.  
  117. int ans[] = { 1, 0, 8, 7, 6, 5, 4, 3, 2 };
  118.  
  119. void show (int idx, int nl, int nr) {
  120. 	node &p = tree[idx];
  121.  
  122. 	if (nl == nr) {
  123. 		printf("%d\n", ans[p.i]);
  124. 		return;
  125. 	}
  126.  
  127. 	propagate(idx, nl, nr);
  128.  
  129. 	int mid = (nl + nr) / 2;
  130. 	show(idx*2+1, nl, mid);
  131. 	show(idx*2+2, mid+1, nr);
  132. }
  133.  
  134. int greatest () {
  135. 	int mx = 0;
  136. 	for (int i = 1; i < 9; i++) {
  137. 		if (fquery[i] >= fquery[mx]) {
  138. 			mx = i;
  139. 		}
  140. 	}
  141. 	return mx;
  142. }
  143.  
  144. int main () {
  145. 	int n, q;
  146. 	scanf("%d %d", &n, &q);
  147.  
  148. 	build(0, 0, n-1);
  149.  
  150. 	for (int i = 0, a, b; i < q; i++) {
  151. 		scanf("%d %d", &a, &b);
  152.  
  153. 		fill(fquery, fquery + 9, 0);
  154. 		query(0, 0, n-1, a, b);
  155. 		int note = greatest();
  156.  
  157. 		if (note) chord(0, 0, n-1, a, b, note);
  158. 	}
  159.  
  160. 	show(0, 0, n-1);
  161.  
  162. 	return 0;
  163. }
Success #stdin #stdout 0.02s 20452KB
comments (?)
stdin
copy 
15 15
10 12
4 5
1 14
6 10
9 11
11 12
9 13
8 9
5 7
11 13
8 10
11 12
11 13
8 14
3 9
stdout
copy 
1
2
2
1
2
6
7
7
8
6
4
4
8
0
4
https://ideone.com/moZuCp
language:
C++14 (gcc 8.3)
created:
5 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!