Submission #1146144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146144		elotelo966	Meteors (POI11_met)	C++20	74 / 100	2363 ms	44140 KiB

met

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define OYY LLONG_MAX
#define mod 1000000007
#define faster ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define FOR for(int i=1;i<=n;i++)
#define mid (start+end)/2
#define lim 600003
#define fi first
#define se second
#define pb push_back
 
vector<pair<int,pair<int,int>>> qu;
 
vector<int> v[lim];
 
int n,m;
 
int dizi[lim],ger[lim],cev[lim],tree[4*lim];
 
inline void build(int node,int start,int end){
	tree[node]=0;
	if(start==end){
		//~ tree[node]=0;
		return ;
	}
	build(node*2,start,mid),build(node*2+1,mid+1,end);
}
 
inline int query(int node,int start,int end,int l,int r){
	if(start>end || start>r || end<l)return 0;
	if(start>=l && end<=r)return tree[node];
	return query(node*2,start,mid,l,r)+query(node*2+1,mid+1,end,l,r);
}
 
inline void update(int node,int start,int end,int l,int r,int val){
	if(start>end || start>r || end<l)return ;
	if(start>=l && end<=r){
		tree[node]+=val;
		return ;
	}
	update(node*2,start,mid,l,r,val),update(node*2+1,mid+1,end,l,r,val);
	tree[node]=tree[node*2]+tree[node*2+1];
}
 
int32_t main(){
	faster
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>dizi[i];
		v[dizi[i]].pb(i);
	}
	
	FOR{
		cev[i]=-1;
		cin>>ger[i];
	}
	
	int q;cin>>q;
	
	for(int i=1;i<=q;i++){
		int l,r,z;cin>>l>>r>>z;
		qu.pb({l,{r,z}});
	}
	
	vector<int> tut;
	FOR{
		tut.pb(i);
	}
	int ind=0;
	
	queue<pair<int,pair<int,vector<int>>>> f;
	
	f.push({0,{q-1,tut}});
		
	while(f.size()){
		int l=f.front().fi,r=f.front().se.fi;
		//cout<<l<<" "<<r<<endl;
		vector<int> cur=f.front().se.se;
		vector<int> v1,v2;
		f.pop();
		assert(l<=r);
		int mi=(l+r)/2;
		if(ind-1>mi){
			build(1,1,m);
			ind=0;
		}
		while(ind<=mi){
			if(qu[ind].fi<=qu[ind].se.fi){
				update(1,1,m,qu[ind].fi,qu[ind].fi,qu[ind].se.se);
				if(qu[ind].se.fi+1<=m)update(1,1,m,qu[ind].se.fi+1,qu[ind].se.fi+1,-qu[ind].se.se);
			}
			else{
				update(1,1,m,qu[ind].fi,qu[ind].fi,qu[ind].se.se);
				update(1,1,m,1,1,qu[ind].se.se);
				if(qu[ind].se.fi+1<=m)update(1,1,m,qu[ind].se.fi+1,qu[ind].se.fi+1,-qu[ind].se.se);
			}
			ind++;
		}
		
		//~ cout<<"k"<<endl;
		
		//~ for(int i=1;i<=m;i++){
			//~ cout<<query(1,1,m,i,i)<<" ";
		//~ }
		
		//~ cout<<endl;
		for(auto a:cur){
			int top=0;
			for(auto x:v[a]){
				top+=query(1,1,m,1,x);
			}
			//cout<<l<<" "<<r<<" "<<mi<<" "<<a<<" "<<top<<endl;
			if(top>=ger[a]){
				v1.pb(a);
			}
			else{
				v2.pb(a);
			}
		}
		
		//~ if(mi==q-1){
			//~ build(1,1,m);
			//~ memset(tree,0,sizeof(tree));
			//~ ind=0;
		//~ }
		
		//~ if(l==r){
			for(auto a:v1){
				cev[a]=mi+1;
			}
			//~ continue;
		//~ }
		//~ else{
			if(l^r){
				if(v1.size())f.push({l,{mi,v1}});
				if(v2.size())f.push({mi+1,{r,v2}});
			}
		//~ }
	}
	
	FOR{
		if(~cev[i])cout<<cev[i]<<'\n';
		else cout<<"NIE"<<'\n';
	}
	
	return 0;
}

• 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: 0 / 13
• Subtask 8: 0 / 13