fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. const int N = 75e3 + 5; 
  12. const int MOD = 1e9; 
  13. const int MX = 1e9;  
  14.  
  15. struct Function {
  16. 	int x1, x2, y1, a, b, y2; 
  17. }; 
  18.  
  19. int n, q; 
  20. Function f[N]; 
  21.  
  22. struct PersistentSegTree {
  23. 	struct Node {
  24. 		int l = 0, r = 0;  
  25. 		ll cnt = 0; 
  26. 		ll sum = 0; 
  27. 	};
  28.  
  29. 	int n; 
  30. 	vector<Node> seg;  
  31.  
  32. 	PersistentSegTree(int n) : n(n) {
  33. 		seg.push_back(Node()); 
  34. 	}
  35.  
  36. 	int update(int pre, int l, int r, int u, int v, ii val) {
  37. 		if (l > v || r < u) return pre; 
  38. 		int cur = seg.size();  
  39. 		seg.push_back(seg[pre]); 
  40. 		if (u <= l && r <= v) {
  41. 			seg[cur].cnt += val.first; 
  42. 			seg[cur].sum += val.second; 
  43. 			return cur; 
  44. 		}
  45. 		int mid = (l + r) >> 1; 
  46. 		seg[cur].l = update(seg[pre].l, l, mid, u, v, val); 
  47. 		seg[cur].r = update(seg[pre].r, mid + 1, r, u, v, val); 
  48. 		return cur; 
  49. 	}
  50.  
  51. 	ll get(int rt, int l, int r, int pos) {
  52. 		if (l > pos || r < pos) return 0;  
  53. 		ll res = seg[rt].cnt * pos + seg[rt].sum;
  54. 		if (l == r) return res;   
  55. 		int mid = (l + r) >> 1; 
  56. 		if (pos <= mid) {
  57. 			res += get(seg[rt].l, l, mid, pos); 
  58. 		}
  59. 		else {
  60. 			res += get(seg[rt].r, mid + 1, r, pos); 
  61. 		}
  62. 		return res; 
  63. 	}
  64.  
  65. 	int update(int pre, int u, int v, ii val) {
  66. 		return update(pre, 1, n, u, v, val);
  67. 	}
  68.  
  69. 	ll get(int rt, int pos) {
  70. 		return get(rt, 1, n, pos);
  71. 	}
  72. }; 
  73.  
  74. int root[N]; 
  75.  
  76. int main() {
  77. 	ios::sync_with_stdio(false); 
  78. 	cin.tie(nullptr); 	
  79. 	cin >> n; 
  80. 	for (int i = 1; i <= n; i++) {
  81. 		int x1, x2, y1, a, b, y2; 
  82. 		cin >> x1 >> x2 >> y1 >> a >> b >> y2; 
  83. 		f[i] = {x1, x2, y1, a, b, y2}; 
  84. 	}
  85.  
  86. 	PersistentSegTree pst(MX); 
  87. 	for (int i = 1; i <= n; i++) {
  88. 		auto [x1, x2, y1, a, b, y2] = f[i]; 
  89. 		root[i] = root[i - 1]; 
  90. 		root[i] = pst.update(root[i], 1, x1, {0, y1}); 
  91. 		root[i] = pst.update(root[i], x1 + 1, x2, {a, b}); 
  92. 		root[i] = pst.update(root[i], x2 + 1, MX, {0, y2}); 
  93. 	}
  94.  
  95. 	cin >> q; 
  96.  
  97. 	ll last = 0;  
  98. 	while (q--) {
  99. 		int l, r, x; 
  100. 		cin >> l >> r >> x;
  101. 		x = (x + last) % MOD; 
  102. 		last = pst.get(root[r], x) - pst.get(root[l - 1], x); 
  103. 		cout << last << '\n';
  104. 	}
  105. }
  106.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
1
1 2 1 4 5 10
1
1 1 2
stdout
copy 
13
https://ideone.com/RDO259
language:
C++14 (gcc 8.3)
created:
13 days 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!