Submission #100123

#	Time	Username	Problem	Language	Result	Execution time	Memory
100123		KLPP	Meteors (POI11_met)	C++14	24 / 100	218 ms	66560 KiB

met

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
int N,M,Q;
vector<int> stations[300005];
lld require[300005];
struct node{
	node *l,*r;
	int x,y;
	lld sum;
};
node *versions[1200005];
int version[300005];
void Start(node *n){
	//cout<<n->x<<" "<<n->y<<endl;
	n->sum=0;
	if(n->x==n->y){
		return;
	}
	n->l=new node();
	n->r=new node();
	n->l->x=n->x;
	n->r->y=n->y;
	int mid=(n->x+n->y)/2;
	n->l->y=mid;
	n->r->x=mid+1;
	//cout<<n->l->x<<" "<<n->l->y<<endl;
	Start(n->l);
	Start(n->r);
}
void Atualizar(node *n, node *m, int pos, lld val){
	if(m->x==m->y){
		m->sum=n->sum;
		m->sum+=val;
		return;
	}
	int mid=(m->x+m->y)/2;
	if(pos<=mid){
		m->r=n->r;
		m->l=new node();
		m->l->x=m->x;
		m->l->y=mid;
		Atualizar(n->l,m->l,pos,val);
		m->sum=m->r->sum+m->l->sum;
	}else{
		m->l=n->l;
		m->r=new node();
		m->r->x=mid+1;
		m->r->y=m->y;
		Atualizar(n->r,m->r,pos,val);
		m->sum=m->r->sum+m->l->sum;		
	}
}
lld query(node *n, int x, int y){
	if(n->y<x || y<n->x)return 0;
	if(x<=n->x && n->y<=y)return n->sum;
	return query(n->l,x,y)+query(n->r,x,y);
}
int main(){
	scanf("%d %d",&N,&M);
	for(int i=0;i<M;i++){
		int x;
		scanf("%d",&x);
		x--;
		stations[x].push_back(i);
	}
	for(int i=0;i<N;i++){
		scanf("%lld",require+i);
	}
	scanf("%d",&Q);
	for(int i=0;i<=4*Q;i++)versions[i]=new node();
	for(int i=0;i<=4*Q;i++){
		versions[i]->x=0;
		versions[i]->y=M;
	}
	Start(versions[0]);
	int cnt=0;
	for(int i=0;i<Q;i++){
		int l,r;
		lld a;
		scanf("%d %d %lld",&l,&r,&a);
		l--;r--;
		if(l<=r){
			Atualizar(versions[cnt],versions[cnt+1],l,a);
			cnt++;
			//version[cnt]=i;
			//cout<<l<<" "<<r<<endl;
			Atualizar(versions[cnt],versions[cnt+1],r+1,-a);
			cnt++;
			//version[cnt]=i;
			//cout<<l<<" "<<r<<endl;
		}else{
			Atualizar(versions[cnt],versions[cnt+1],l,a);
			cnt++;
			//version[cnt]=i;
			Atualizar(versions[cnt],versions[cnt+1],M,-a);
			cnt++;
			//version[cnt]=i;
			Atualizar(versions[cnt],versions[cnt+1],0,a);
			cnt++;
			//version[cnt]=i;
			Atualizar(versions[cnt],versions[cnt+1],r+1,-a);
			cnt++;
			//version[cnt]=i;			
		}
		version[i]=cnt;
		//cout<<cnt<<endl;
	}
	/*for(int i=0;i<Q;i++){
		cout<<query(versions[version[i]],0,0)<<" "<<query(versions[version[i]],0,3)<<endl;
	}*/
	for(int i=0;i<N;i++){
		int lo=-1;
		int hi=Q;
		/*for(int j=0;j<stations[i].size();j++){
			cout<<stations[i][j]<<" ";
		}cout<<endl;*/
		while(hi-lo>1){
			int mid=(hi+lo)/2;
			//cout<<lo<<" "<<hi<<" "<<mid<<endl;
			lld samples=0;
			for(int j=0;j<stations[i].size();j++){
				samples+=query(versions[version[mid]],0,stations[i][j]);
			}//cout<<samples<<" A "<<mid<<endl;
			if(samples>=require[i]){
				hi=mid;
			}else lo=mid;
		}
		if(hi<Q){
			printf("%d\n",hi+1);
		}else printf("NIE\n");
	}
	return 0;
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:123:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j=0;j<stations[i].size();j++){
                ~^~~~~~~~~~~~~~~~~~~
met.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
  ~~~~~^~~~~~~~~~~~~~~
met.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~
met.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",require+i);
   ~~~~~^~~~~~~~~~~~~~~~~~
met.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&Q);
  ~~~~~^~~~~~~~~
met.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld",&l,&r,&a);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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