fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define lowbit(x) (x & -x)
  4. long long n, m, k;
  5. vector <long long> o[300010];
  6. long long p[300010], l[300010], r[300010], a[300010], ans[300010];
  7. struct BIT
  8. {
  9. 	long long node[300010];
  10. 	void upd(long long pos,long long k) {
  11. 		for(long long i = pos;i <= 300005;i += lowbit(i)) node[i] += k;
  12. 	}
  13. 	long long qry(long long pos) {
  14. 		long long res = 0;
  15. 		for(long long i = pos;i > 0;i -= lowbit(i)) res += node[i];
  16. 		return res;
  17. 	}
  18. } wlx;
  19. void arr_add_sec(long long l1, long long r1, long long add_num)
  20. {
  21. 	wlx.upd(l1, add_num);
  22. 	wlx.upd(r1 + 1, -add_num);
  23. }
  24. void ring_add_sec(long long l1, long long r1, long long add_num)
  25. {
  26. 	if (l1 > r1){arr_add_sec(l1, m, add_num); arr_add_sec(1, r1, add_num);}
  27. 	else arr_add_sec(l1, r1, add_num);
  28. }
  29. void work(long long l1, long long r1, vector <long long> now)
  30. {
  31. 	if (l1 == r1) {for (auto x : now) ans[x] = l1;return;}
  32. 	long long mid = (l1 + r1) / 2;
  33. 	for (long long i = l1; i <= mid; i++)
  34. 		ring_add_sec(l[i], r[i], a[i]);
  35. 	vector <long long> left, right;
  36. 	for (auto x : now)
  37. 	{
  38. 		long long sum = 0;
  39. 		for (auto y : o[x])
  40. 			sum += wlx.qry(y);
  41. 		if (sum < p[x]) {p[x] -= sum; right.push_back(x);}
  42. 		else left.push_back(x);
  43. 	}
  44. 	for (long long i = l1; i <= mid; i++)
  45. 		ring_add_sec(l[i], r[i], -a[i]);
  46. 	work(l1, mid, left);
  47. 	work(mid + 1, r1, right);
  48. }
  49. int main()
  50. {
  51. 	cin >> n >> m;
  52. 	for (long long i = 1; i <= m; i++)
  53. 	{
  54. 		long long o1;
  55. 		cin >> o1;
  56. 		o[o1].push_back(i);
  57. 	}
  58. 	for (long long i = 1; i <= n; i++) cin >> p[i];
  59. 	cin >> k;
  60. 	for (long long i = 1; i <= k; i++) cin >> l[i] >> r[i] >> a[i];
  61. 	vector <long long> all;
  62. 	for (long long i = 1; i <= n; i++) all.push_back(i);
  63. 	work(1, k + 1, all);
  64. 	for (long long i = 1; i <= n; i++)
  65. 	{
  66. 		if (ans[i] == k + 1) {puts("NIE"); continue;}
  67. 		cout << ans[i] << endl;
  68. 	}
  69. 	return 0;
  70. }
Success #stdin #stdout 0.01s 11604KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Gfo3Eg
language:
C++14 (gcc 8.3)
created:
1 day 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!