Submission #1012956

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012956		vjudge1	Meteors (POI11_met)	C++14	100 / 100	592 ms	65536 KiB

met

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define max(a,b) ((a)<(b)?(b):(a))
#define min(a,b) ((a)>(b)?(b):(a))
#define tomax(a,b) ((a)=max((a),(b)))
#define tomin(a,b) ((a)=min((a),(b)))
#define RCL(a,b,c,d) memset((a),(b),sizeof(c)*(d))
#define FOR(i,a,b) for(register int i=(a);i<=(b);++i)
#define DOR(i,a,b) for(register int i=(a);i>=(b);--i)
#define EDGE(g,i,u,x) for(register int (i)=(g).h[(u)],(x)=(g).v[(i)];(i);(i)=(g).nxt[(i)],(x)=(g).v[(i)])
#define main Main();signed main(){ios::sync_with_stdio(0);cin.tie(0);return Main();}signed Main
using namespace std;
constexpr int N=3e5+10;
int n,m,t,tot;
int a[N],p[N],ans[N];
ll sum[N];
struct Modify{
	int x,t,v;
	friend bool operator <(Modify a,Modify b){
		return a.x<b.x;
	}
};
#define mid (l+r>>1)
void Bound(int l,int r,vector<Modify> &mo,vector<int> &vec){
	for(const int &x:vec)sum[a[x]]=0;
	if(l==r){
		int it=0;
		ll Sum=0;
		for(const int &x:vec){
			for(;it<mo.size()&&mo[it].x<=x;++it)Sum+=mo[it].v;
			if(sum[a[x]]<p[a[x]])sum[a[x]]+=Sum;
		}
		for(const int &x:vec)ans[a[x]]=(sum[a[x]]>=p[a[x]]?l:-1);
		return mo.clear(),vec.clear();
	}
	vector<Modify> Ls,Rs;
	vector<int> ls,rs;
	for(const Modify &x:mo)(x.t<=mid?Ls:Rs).push_back(x);
	mo.clear();
	int it=0;
	ll Sum=0;
	for(const int &x:vec){
		for(;it<Ls.size()&&Ls[it].x<=x;++it)Sum+=Ls[it].v;
		if(sum[a[x]]<p[a[x]])sum[a[x]]+=Sum;
	}
	for(const int &x:vec)(sum[a[x]]>=p[a[x]]?ls:rs).push_back(x);
	vec.clear();
	for(const int &x:rs)if(~sum[a[x]])p[a[x]]-=sum[a[x]],sum[a[x]]=-1;
	Bound(l,mid,Ls,ls),Bound(mid+1,r,Rs,rs);
}
#undef mid
signed main(){
	cin>>n>>m;
	FOR(i,1,m)cin>>a[i];
	FOR(i,1,n)cin>>p[i],ans[i]=-1;
	vector<int> vec(m);
	vector<Modify> mo;
	cin>>t;
	FOR(i,1,t){
		int l,r,a;cin>>l>>r>>a,++r;
		if(l<r){
			mo.push_back({l,i,a});
			if(r<=m)mo.push_back({r,i,-a});
		}else{
			mo.push_back({1,i,a});
			if(l^r)mo.push_back({r,i,-a}),mo.push_back({l,i,a});
		}
	}
	iota(vec.begin(),vec.end(),1),sort(mo.begin(),mo.end());
	Bound(1,t,mo,vec);
	FOR(i,1,n){
		if(~ans[i])cout<<ans[i]<<endl;
		else cout<<"NIE"<<endl;
	}
	return 0;
}

Compilation message (stderr)

met.cpp: In function 'void Bound(int, int, std::vector<Modify>&, std::vector<int>&)':
met.cpp:31:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Modify>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |    for(;it<mo.size()&&mo[it].x<=x;++it)Sum+=mo[it].v;
      |         ~~^~~~~~~~~~
met.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 | #define mid (l+r>>1)
      |              ~^~
met.cpp:39:31: note: in expansion of macro 'mid'
   39 |  for(const Modify &x:mo)(x.t<=mid?Ls:Rs).push_back(x);
      |                               ^~~
met.cpp:44:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Modify>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(;it<Ls.size()&&Ls[it].x<=x;++it)Sum+=Ls[it].v;
      |        ~~^~~~~~~~~~
met.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 | #define mid (l+r>>1)
      |              ~^~
met.cpp:50:10: note: in expansion of macro 'mid'
   50 |  Bound(l,mid,Ls,ls),Bound(mid+1,r,Rs,rs);
      |          ^~~
met.cpp:24:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 | #define mid (l+r>>1)
      |              ~^~
met.cpp:50:27: note: in expansion of macro 'mid'
   50 |  Bound(l,mid,Ls,ls),Bound(mid+1,r,Rs,rs);
      |                           ^~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13