fork download
copy 
  1. #include <bits/stdc++.h>
  2. bool multitest = false;
  3. #define ll long long
  4. #define db double
  5. #define pb push_back
  6. #define pii pair<int,int>
  7. #define vi vector<int>
  8. #define pli pair<ll,int>
  9. #define ALL(A) (A).begin(), (A).end()
  10. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  11. #define file(Roxy) if(fopen(Roxy".inp", "r")){freopen(Roxy".inp", "r", stdin);freopen(Roxy".out", "w", stdout);}
  12. #define fi first
  13. #define se second
  14. #define mp make_pair
  15. #define FOR(i, a, b) for(int i = (a); i <= (b); i++)
  16. #define FORD(i, a, b) for(int i = (a); i >= (b); i--)
  17. #define FORN(i, a, b) for(int i = (a); i < (b); i++)
  18. ll sq(ll a){return a*a;}  
  19. ll gcd(ll a, ll b){return b ==0 ? a: gcd(b,a%b);} 
  20. ll lcm(ll a, ll b){return a/gcd(a,b)*b;}
  21. template <class T1,class G2>bool maxi(T1 &a, const G2 b){if(a < b){a = b;return 1;} return 0;}
  22. template <class T1,class G2>bool mini(T1 &a, const G2 b){if(a > b){a = b;return 1;} return 0;}
  23. using namespace std;
  24.  
  25. const int N = 3e5 + 5, oo = 2e9, CH = 26, LG = __lg(N) + 1;
  26. const ll inf = 1e18, base = 331, sm = 1e9 + 7;
  27.  
  28. int n, m, q;
  29. long long a[N], p[N];
  30. struct bg {
  31. 	int l, r;
  32. 	long long val;
  33. } Q[N];
  34. vi pos[N];
  35.  
  36. void init() {
  37. 	cin >> n >> m;
  38. 	FOR(i, 1, m) cin >> a[i];
  39. 	FOR(i, 1, m) pos[a[i]].push_back(i);
  40. 	FOR(i, 1, n) cin >> p[i];
  41. 	cin >> q;
  42. 	FOR(i, 1, q) cin >> Q[i].l >> Q[i].r >> Q[i].val;
  43. }
  44.  
  45. ll bit[N];
  46.  
  47. void up(int pos, ll val) {
  48. 	for(int i = pos; i <= m; i+=i&-i) bit[i]+= val;
  49. }
  50.  
  51. ll get(int u) {
  52. 	ll sum = 0;
  53. 	for(int i = u; i; i-=i&-i) sum+= bit[i];
  54. 	return sum;
  55. }
  56.  
  57. ll get(int l, int r) {
  58. 	return get(r) - get(l - 1);
  59. }
  60.  
  61. int L[N], R[N], ans[N];
  62. vi Quer[N];
  63.  
  64. void solve() {
  65. 	FOR(i, 1, n) L[i] = 1, R[i] = q;
  66. 	memset(ans, - 1, sizeof ans);
  67.  
  68. 	while(1) {
  69. 		bool ok = false;
  70. 		FOR(i, 1, n) if(L[i] <= R[i]) {
  71. 			Quer[(L[i] + R[i]) >> 1].push_back(i);
  72. 			ok = true;
  73. 		}
  74. 		if(ok == false) break;
  75.  
  76. 		FOR(i, 1, q) {
  77. 			int l = Q[i].l, r = Q[i].r; ll val = Q[i].val;
  78. 			if(l <= r) {
  79. 				// update(1, 1, m, l, r, val);
  80. 				up(l, val);
  81. 				up(r + 1, - val);
  82. 			} else {
  83. 				// update(1, 1, m, l, m, val);
  84. 				// update(1, 1, m, 1, r, val);
  85. 				up(l, val);
  86. 				up(1, val);
  87. 				up(r + 1, - val);
  88. 			}
  89.  
  90. 			for(const int &id : Quer[i]) {
  91. 				ll sum = 0;
  92. 				for(const int &v : pos[id]) sum+= get(v, v);
  93. 				if(sum >= p[id]) {
  94. 					ans[id] = i;
  95. 					R[id] = i - 1;
  96. 				} else L[id] = i + 1;
  97. 			}
  98. 		}
  99.  
  100. 		FOR(i, 0, m) bit[i] = 0;
  101. 		FOR(i, 0, q) Quer[i].clear();
  102. 	}
  103.  
  104. 	FOR(i, 1, n) cout << ans[i] << '\n';
  105. }
  106.  
  107. signed main() {
  108.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  109.     file("saobang");
  110.     int test = 1;
  111.     if(multitest) cin >> test;
  112.     FOR(i, 1, test) {
  113.         init();
  114.         solve();
  115.     }
  116.     return void(cerr << "\nTime elapsed : " << TIME << "s "), 0;
  117. }
Success #stdin #stdout #stderr 0.01s 20728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Time elapsed : 0.008815s
https://ideone.com/HDu3Dk
language:
C++ (gcc 8.3)
created:
7 days 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!