Submission #32128

#	Time	Username	Problem	Language	Result	Execution time	Memory
32128		dereotu	Meteors (POI11_met)	C++14	100 / 100	3309 ms	61548 KiB

met

#include <bits/stdc++.h>
#define endl '\n'
#define space ' '
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define ii pair <int,int>
#define iii pair <int,pair<int,int> >
#define vi vector <int>
#define vii vector < pair<int,int> >
#define forr(i,A,B) for(int i=A;i<B;++i)
#define input(file) freopen(file,"r",stdin)
#define output(file) freopen(file,"w",stdout)
#define time hdsadas
#define edge xasdafsaf
#define y1 dsafgsdfs
#define MAXX 10
#define mod 1000000007
using namespace std;
typedef pair<pair<int,int>,pair<int,int> > edge;
 
inline void read(int &x){
	scanf(" %d",&x);
}
const int maxn=3*100005;

vector <int> owner[maxn],tocheck[maxn];
int n,m,k,ql[maxn],qr[maxn],lo[maxn],hi[maxn],x;
long long sum,fw[maxn],need[maxn],qa[maxn];

void upd(int x,long long val){
	if(x==0) return;
	for(;x<=m;x+=(x&-x)){
		fw[x]+=val;
	}
}

long long que(int x){
	long long ret=0;
	for(;x>0;x-=(x&-x))
		ret+=fw[x];
	return ret;
}

void shower(int x){
	if(ql[x]<=qr[x]){
		upd(ql[x],qa[x]);
		upd(qr[x]+1,-qa[x]);
	}
	else{
		upd(1,qa[x]);
		upd(qr[x]+1,-qa[x]);
		upd(ql[x],qa[x]);
	}
}
#undef int
int main(){
	#define int long long
	//ios_base::sync_with_stdio(false);
	//cin.tie(0);
	cin>>n>>m;
	forr(i,0,m){
		int x;
		cin>>x;
		owner[x].pb(i+1);
	}
	forr(i,0,n){
		cin>>need[i+1];
	}
	cin>>k;
	forr(i,1,k+1){
		cin>>ql[i]>>qr[i]>>qa[i];
	}
	forr(i,1,n+1){
		lo[i]=1;
		hi[i]=k+1;
	}
	bool notdone=true;
	while(notdone){
		notdone=false;
		memset(fw,0,sizeof fw);
		forr(i,1,n+1){
			if(lo[i]!=hi[i]) tocheck[(lo[i]+hi[i])/2].pb(i);
		}
		forr(i,1,k+1){
			shower(i);
			while(!tocheck[i].empty()){
				notdone=true;
				sum=0;
				int id=tocheck[i].back();
				tocheck[i].pop_back();
				forr(j,0,owner[id].size()){
					sum+=que(owner[id][j]);
					assert(sum>=0);
					if(sum>=need[id]) break;
				}
				if(sum>=need[id]){
					hi[id]=i;
				}
				else{
					lo[id]=i+1;
				}
			}
		}
	}
	forr(i,1,n+1){
		if(lo[i]==k+1) cout<<"NIE\n";
		else cout<<lo[i]<<endl;
	}
	return 0;
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:12:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define forr(i,A,B) for(int i=A;i<B;++i)
                                  ^
met.cpp:93:5: note: in expansion of macro 'forr'
     forr(j,0,owner[id].size()){
     ^

• 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