fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FOR(i,a,b) for(lli i=(lli)a;i<=(lli)b;i++)
  4. #define endl "\n"
  5. #define mp make_pair
  6. #define X first
  7. #define Y second
  8. #define inf 1e18
  9. #define mod 1000000007
  10. #define pb push_back
  11. #define pi 3.14159265359
  12. #define gc getchar
  13. #define Case cout<<"Case #"<<++cas<<": ";
  14. #define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  15. #define all(v) v.begin(),v.end()
  16. #define eb emplace_back
  17. // #define lli int
  18. typedef long long int lli;
  19. typedef pair<int,int> pii;
  20. typedef pair<lli,int> pli;
  21. typedef vector<pii> vii;
  22. typedef pair<lli,lli> pll;
  23. typedef vector<lli> vl;
  24. typedef vector<int> vi;
  25. typedef vector<vi> vvi;
  26. typedef vector<vl> vvl;
  27.  
  28. #define pr(...) dbs(#__VA_ARGS__, __VA_ARGS__)
  29. template <class T> void dbs(string str, T t) {cerr << str << " : " << t << "\n";}
  30. template <class T, class... S> void dbs(string str, T t, S... s) {int idx = str.find(','); cerr << str.substr(0, idx) << " : " << t << ","; dbs(str.substr(idx + 1), s...);}
  31. template <class S, class T>ostream& operator <<(ostream& os, const pair<S, T>& p) {return os << "(" << p.first << ", " << p.second << ")";}
  32. template <class T>ostream& operator <<(ostream& os, const vector<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
  33. template <class T>ostream& operator <<(ostream& os, const set<T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
  34. template <class S, class T>ostream& operator <<(ostream& os, const map<S, T>& p) {os << "[ "; for (auto& it : p) os << it << " "; return os << "]";}
  35. template <class T> void prc(T a, T b) {cerr << "["; for (T i = a; i != b; ++i) {if (i != a) cerr << ", "; cerr << *i;} cerr << "]\n";}
  36.  
  37. lli n,m,P[300009],S[300009],ans[300009];
  38. pll Q[300009];
  39. vl A[300009];
  40.  
  41. struct SegTree
  42. {
  43. 	vl v;
  44. 	SegTree(lli n):v(4*n){}
  45. 	SegTree(){}
  46.  
  47. 	void rangeupdate(lli ind,lli a,lli b,lli l,lli r,lli x)
  48. 	{
  49. 		if(a>b || l>r || r<a || l>b) return;
  50. 		if(l<=a && r>=b) {v[ind]+=x;return;}
  51. 		lli mid=(a+b)/2;
  52. 		rangeupdate(ind<<1,a,mid,l,r,x);
  53. 		rangeupdate((ind<<1)+1,mid+1,b,l,r,x);
  54. 	}
  55.  
  56. 	lli query(lli ind,lli a,lli b,lli qin)
  57. 	{
  58. 		// pr(ind,a,b,qin);
  59. 		if(a>b || qin<a || qin>b) return 0;
  60. 		if(a==b) return v[ind];
  61. 		lli mid=(a+b)/2;
  62. 		return v[ind]+query(ind<<1,a,mid,qin)+query((ind<<1)+1,mid+1,b,qin);
  63. 	}
  64. };
  65.  
  66. SegTree T;
  67.  
  68. void apply(lli ind,lli sign)
  69. {
  70. 	// pr(ind,sign,Q[ind],S[ind]);
  71. 	if(Q[ind].X<=Q[ind].Y)
  72. 		T.rangeupdate(1,1,m,Q[ind].X,Q[ind].Y,sign*S[ind]);
  73. 	else
  74. 	{
  75. 		T.rangeupdate(1,1,m,1,Q[ind].Y,sign*S[ind]);
  76. 		T.rangeupdate(1,1,m,Q[ind].X,m,sign*S[ind]);
  77. 	}
  78. 	// FOR(i,1,5) pr(T.query(1,1,m,i));
  79. }
  80.  
  81. lli query(lli ind)
  82. {
  83. 	lli ret = T.query(1,1,m,ind);
  84. 	// pr(ind,ret);
  85. 	return ret;
  86. }
  87.  
  88. void solve(lli l,lli r,vl& v,lli nq)
  89. {
  90. 	// pr(l,r,v,nq);
  91. 	if(v.empty() || l>r) return;
  92. 	lli mid=(l+r)/2;
  93. 	if(nq<mid)
  94. 		FOR(i,nq+1,mid)
  95. 		apply(i,1);
  96. 	else
  97. 		FOR(i,mid+1,nq)
  98. 		apply(i,-1);
  99. 	vl lv,rv;
  100. 	for(lli i:v)
  101. 	{
  102. 		lli sum=0;
  103. 		for(lli j:A[i])
  104. 			sum+=query(j);
  105. 		if(sum>=P[i])
  106. 			{ans[i]=min(ans[i],mid);lv.pb(i);}
  107. 		else rv.pb(i);
  108. 	}
  109. 	if(l!=r){solve(l,mid,lv,mid);
  110. 	solve(mid+1,r,rv,mid);}
  111. 	if(nq<mid)
  112. 		FOR(i,nq+1,mid)
  113. 		apply(i,-1);
  114. 	else
  115. 		FOR(i,mid+1,nq)
  116. 		apply(i,1);
  117. }
  118.  
  119. int main()
  120. {
  121. 	fastio;
  122. 	lli a,k,l,r;vl v;
  123. 	cin>>n>>m;
  124. 	T=SegTree(m);
  125. 	FOR(i,1,n)
  126. 	ans[i]=inf;
  127. 	FOR(i,1,m)
  128. 	{
  129. 		cin>>a;
  130. 		A[a].pb(i);
  131. 	}
  132. 	FOR(i,1,n)
  133. 	cin>>P[i];
  134. 	cin>>k;
  135. 	FOR(i,1,k)
  136. 	{
  137. 		cin>>l>>r>>a;
  138. 		Q[i]=mp(l,r);
  139. 		S[i]=a;
  140. 	}
  141. 	FOR(i,1,n) v.pb(i);
  142. 	solve(1,k,v,0);
  143. 	FOR(i,1,n)
  144. 	if(ans[i]!=inf)
  145. 		cout<<ans[i]<<endl;
  146. 	else cout<<"NIE"<<endl;
  147. }
Runtime error #stdin #stdout 0.01s 34824KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Ix7Z4R
language:
C++14 (gcc 8.3)
created:
7 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!