fork(1) download
copy 
  1. #include<iostream>
  2. using namespace std;
  3. long long x[200000], n, q;
  4. int main() {
  5. 	cin >> n >> q; x[0] = 2000000000000;
  6. 	if (n <= 100 && q <= 100) {
  7. 		for (int i = 0; i < q; i++) {
  8. 			long long a, b, t = 0;
  9. 			cin >> a >> b;
  10. 			bool flag = false;
  11. 			for (int j = a; j >= 1; j--) {
  12. 				if (j != 1)t += (x[j - 1] - x[j])*(a - j + 1);
  13. 				if (t >= b || j == 1) {
  14. 					if (j != 1) t -= (x[j - 1] - x[j])*(a - j + 1);
  15. 					for (int k = j + 1; k <= a; k++)x[k] = x[j];
  16. 					long long u = b - t;
  17. 					long long v1 = u / (a - j + 1), v2 = u % (a - j + 1);
  18. 					for (int k = j; k < j + v2; k++)x[k] += (v1 + 1);
  19. 					for (int k = j + v2; k <= a; k++)x[k] += v1;
  20. 					flag = true;
  21. 					break;
  22. 				}
  23. 			}
  24. 		}
  25. 	}
  26. 	else {
  27. 		for (int i = 0; i < q; i++) {
  28. 			long long a, b;
  29. 			cin >> a >> b;
  30. 			for (int j = 0; j < b; j++) {
  31. 				int L = 1, R = a, M;
  32. 				if (x[a] != x[a - 1]) { x[a]++; continue; }
  33. 				if (x[a] == x[1]) { x[1]++; continue; }
  34. 				while (true) {
  35. 					M = (L + R) / 2;
  36. 					if (x[a] == x[M] && x[a] != x[M - 1]) { x[M]++; break; }
  37. 					if (x[a] == x[M - 1])R = M;
  38. 					if (x[a] != x[M])L = M;
  39. 				}
  40. 			}
  41. 		}
  42. 	}
  43. 	for (int i = 1; i <= n; i++)cout << x[i] << endl;
  44. 	return 0;
  45. }
Success #stdin #stdout 0s 5036KB
comments (?)
stdin
copy 
6 6
1 1
2 1
3 1
4 1
5 1
6 1
stdout
copy 
1
1
1
1
1
1
https://ideone.com/ym3XCQ
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!