Submission #100128

# Submission time Handle Problem Language Result Execution time Memory
100128 2019-03-09T10:53:48 Z KLPP Meteors (POI11_met) C++14
24 / 100
256 ms 66560 KB
#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[600005];
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<=2*Q;i++)versions[i]=new node();
	for(int i=0;i<=2*Q;i++){
		versions[i]->x=0;
		versions[i]->y=M;
	}
	Start(versions[0]);
	int cnt=0;
	lld add[Q+1];
	add[0]=0;
	for(int i=0;i<Q;i++){
		int l,r;
		lld a;
		scanf("%d %d %lld",&l,&r,&a);
		l--;r--;
		add[i+1]=add[i];
		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++;
			Atualizar(versions[cnt],versions[cnt+1],r+1,-a);
			cnt++;
			add[i+1]+=a;			
		}
		version[i]=cnt;
		//cout<<add[i+1]<<endl;
		//cout<<cnt<<endl;
	}
	/*for(int i=0;i<Q;i++){
		cout<<query(versions[version[i]],0,4)+add[i+1]<<" "<<query(versions[version[i]],0,3)+add[i+1]<<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])+add[mid+1];
			}//cout<<samples<<" A "<<mid<<" "<<add[mid+1]<<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

met.cpp: In function 'int main()':
met.cpp:120: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:84: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);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 12 ms 8576 KB Output is correct
2 Correct 11 ms 8576 KB Output is correct
3 Correct 11 ms 8576 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 10 ms 8448 KB Output is correct
2 Correct 11 ms 8448 KB Output is correct
3 Correct 10 ms 8576 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 161 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 169 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 111 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 171 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 256 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 219 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -