oj.uz

Submission #100123

# Submission time Handle Problem Language Result Execution time Memory
100123 2019-03-09T10:25:38 Z KLPP Meteors (POI11_met) C++14
24 / 100
 218 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[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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 9088 KB Output is correct
2 Correct 11 ms 9088 KB Output is correct
3 Correct 15 ms 9088 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 8960 KB Output is correct
2 Correct 14 ms 9088 KB Output is correct
3 Correct 15 ms 9120 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 158 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 164 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 112 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 138 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 218 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 204 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -