fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using tii = tuple<int, int, int>;
  4.  
  5. const int mxn = 3e5 + 5;
  6. int n, k, ev, a, b, c;
  7. tii event[mxn];
  8. vector<int> space[mxn], st;
  9. int ans[mxn], tgt[mxn];
  10. int fenw[mxn];
  11.  
  12. void ubas(int idx, int val) {
  13. 	for(;idx<=k;idx+=idx&-idx)
  14. 		fenw[idx] += val;
  15. }
  16. void upd(int l, int r, int val) {
  17. 	ubas(l, val); ubas(r+1, -val);
  18. 	if(l > r) ubas(1, val);
  19. }
  20.  
  21. int qr(int idx) {
  22. 	int sum = 0;
  23. 	for(;idx>0;idx-=idx&-idx)
  24. 		sum += fenw[idx];
  25. 	return sum;
  26. }
  27.  
  28. void bs(int lt, int rt, vector<int>& tofind) {
  29. 	if(lt > rt || tofind.empty()) {
  30. 		for(int e:tofind) /*cout << "SETTED " << e << " TO " << lt << '\n', */ans[e] = lt;
  31. 		return;
  32. 	}
  33. 	int mt = (lt + rt) >> 1;
  34. 	for(int i=lt;i<=mt;i++) {
  35. 		tie(a, b, c) = event[i];
  36. 		upd(a, b, c);
  37. 	}
  38. 	vector<int> fin, notfin;
  39. 	//cout << mt << " : " << '\n';
  40. 	//for(int i=1;i<=k;i++) cout << qr(i) << ' ' ;
  41. 	//cout << ":\n";
  42. 	for(int e:tofind) {
  43. 		int sum = 0;
  44. 		for(int v:space[e]) sum += qr(v); 
  45. 		if(sum < tgt[e]) notfin.push_back(e);
  46. 		else fin.push_back(e);
  47. 		//cout << e << " : " << sum << '\n';
  48. 	}
  49. 	bs(mt+1, rt, notfin);
  50. 	for(int i=mt;i>=lt;i--) {
  51. 		tie(a, b, c) = event[i];
  52. 		upd(a, b, -c);
  53. 	}
  54. 	bs(lt, mt-1, fin);
  55. }
  56.  
  57. int main() {
  58. 	scanf("%d %d", &n, &k);
  59. 	for(int i=1;i<=k;i++) {
  60. 		scanf("%d", &a);
  61. 		space[a-1].push_back(i);
  62. 	}
  63. 	st = vector<int>(n);
  64. 	for(int i=0;i<n;i++)
  65. 		st[i] = i, scanf("%d", &tgt[i]);
  66. 	scanf("%d", &ev);
  67. 	for(int i=1;i<=ev;i++) {
  68. 		scanf("%d %d %d", &a, &b, &c);
  69. 		event[i] = tie(a, b, c);
  70. 	}
  71. 	bs(1, ev, st);
  72. 	for(int i=0;i<n;i++) {
  73. 		//cout << ans[i] << ' ';
  74. 		if(ans[i]<=ev) printf("%d\n", ans[i]);
  75. 		else printf("sad\n");
  76. 	}
  77. }
Success #stdin #stdout 0.01s 13960KB
comments (?)
stdin
copy 
3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2
stdout
copy 
3
sad
1
https://ideone.com/4MpAaN
language:
C++14 (gcc 8.3)
created:
1 year 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!