fork(1) download
copy 
  1. #include <vector>
  2. #include <iostream>
  3. #include <algorithm>
  4. using namespace std;
  5. #pragma warning(disable : 4996)
  6.  
  7. class LazySegmentTree {
  8. private:
  9. 	int size_;
  10. 	vector<long long> v, lazy;
  11. 	void update(int a, int b, long long x, int k, int l, int r) {
  12. 		push(k, l, r);
  13. 		if (r <= a || b <= l) return;
  14. 		if (a <= l && r <= b) {
  15. 			lazy[k] = x;
  16. 			push(k, l, r);
  17. 		}
  18. 		else {
  19. 			update(a, b, x, k * 2, l, (l + r) >> 1);
  20. 			update(a, b, x, k * 2 + 1, (l + r) >> 1, r);
  21. 			v[k] = merge(v[k * 2], v[k * 2 + 1]);
  22. 		}
  23. 	}
  24. 	long long query(int a, int b, int k, int l, int r) {
  25. 		push(k, l, r);
  26. 		if (r <= a || b <= l) return 0;
  27. 		if (a <= l && r <= b) return v[k];
  28. 		long long lc = query(a, b, k * 2, l, (l + r) >> 1);
  29. 		long long rc = query(a, b, k * 2 + 1, (l + r) >> 1, r);
  30. 		return merge(lc, rc);
  31. 	}
  32.  
  33. public:
  34. 	LazySegmentTree() : v(vector<long long>()), lazy(vector<long long>()) {};
  35. 	LazySegmentTree(int n) {
  36. 		for (size_ = 1; size_ < n;) size_ <<= 1;
  37. 		v.resize(size_ * 2);
  38. 		lazy.resize(size_ * 2);
  39. 	}
  40. 	inline void push(int k, int l, int r) {
  41. 		if (lazy[k] != 0) {
  42. 			v[k] = lazy[k] * (r - l);
  43. 			if (r - l > 1) {
  44. 				lazy[k * 2] = lazy[k];
  45. 				lazy[k * 2 + 1] = lazy[k];
  46. 			}
  47. 			lazy[k] = 0;
  48. 		}
  49. 	}
  50. 	inline long long merge(long long x, long long y) {
  51. 		return x + y;
  52. 	}
  53. 	inline void update(int l, int r, long long x) {
  54. 		update(l, r, x, 1, 0, size_);
  55. 	}
  56. 	inline long long query(int l, int r) {
  57. 		return query(l, r, 1, 0, size_);
  58. 	}
  59. };
  60.  
  61. int N, Q, a; long long b; LazySegmentTree seg;
  62. inline long long solve(int p) {
  63. 	long long x = (a - p) * seg.query(p, p + 1);
  64. 	long long y = seg.query(p, a);
  65. 	return x - y;
  66. }
  67. int main() {
  68. 	cin >> N >> Q;
  69. 	seg = LazySegmentTree(N);
  70. 	while (Q--) {
  71. 		cin >> a >> b;
  72. 		int l = 0, r = a;
  73. 		while (r - l > 1) {
  74. 			int m = (l + r) >> 1;
  75. 			if (solve(m) > b) l = m;
  76. 			else r = m;
  77. 		}
  78. 		if (solve(l) > b) l++;
  79. 		long long v = seg.query(l, a) + b;
  80. 		seg.update(l, l + v % (a - l), v / (a - l) + 1);
  81. 		seg.update(l + v % (a - l), a, v / (a - l));
  82. 		//for (int i = 0; i < N; i++) cout << seg.query(i, i + 1) << ' ';
  83. 		//cout << endl;
  84. 	}
  85. 	for (int i = 0; i < N; i++) cout << seg.query(i, i + 1) << endl;
  86. 	return 0;
  87. }
Success #stdin #stdout 0s 3488KB
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/s1fPCc
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!