oj.uz

Submission #102731

# Submission time Handle Problem Language Result Execution time Memory
102731 2019-03-27T09:47:21 Z bakpark Meteors (POI11_met) C++14
74 / 100
 5389 ms 66560 KB 
#include <cstdio>
#include <algorithm>
#include <memory.h>
#include <vector>
using namespace std;
#define ll long long
struct quer{
	int l,r;
	ll val;
};

int N,M,Q;
ll tree[1200000];
ll need[300005];
quer q[300005];
vector<int> arr[300005];
vector<int> bs[300005];
int L[300005],R[300005],answ[300005];
int MAX=1;

void push(int x,int l,int r,int LL,int RR,ll val){
	if(r<LL||RR<l) return;
	if(LL<=l&&r<=RR){
		tree[x]+=val;
		return;
	}
	int m = (l+r)>>1;
	push(x<<1,l,m,LL,RR,val);
	push((x<<1)+1,m+1,r,LL,RR,val);
}
ll get(int pos){
	ll sum = 0;
	int x = MAX-1+pos;
	while(x>0){
		sum+=tree[x];
		x = x>>1;
	}
	return sum;
}

int main(){
	scanf("%d %d",&N,&M);
	while(MAX<M){
		MAX = MAX<<1;
	}
	for(int i=1;i<=M;i++){
		int tmp;
		scanf("%d",&tmp);
		arr[tmp].push_back(i);
	}
	for(int i=1;i<=N;i++) scanf("%lld",&need[i]);
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++) {
		scanf("%d %d %lld",&q[i].l,&q[i].r,&q[i].val);
	}
	for(int i=1;i<=N;i++){
		L[i] = 1;
		R[i] = Q;
		answ[i] = -1;
		bs[(Q+1)>>1].push_back(i);
	}
	bool flag = true;
	while(flag){
		memset(tree,0,sizeof(tree));
		flag = false;
		for(int i=1;i<=Q;i++){
			int l = q[i].l,r = q[i].r;
			ll val = q[i].val;
			if(l<=r){
				push(1,1,MAX,l,r,val);
			}
			else{
				push(1,1,MAX,l,M,val);
				push(1,1,MAX,1,r,val);
			}
			for(int ver:bs[i]){
				ll sum = 0;
				bool done = false;
				for(int pos:arr[ver]){
					sum+=get(pos);
					if(sum>=need[ver]){
						R[ver] = i-1;
						answ[ver] = i;
						done = true;
						break;
					}
				}
				if(!done) L[ver] = i+1;
				if(L[ver]<=R[ver]){
					int m = (L[ver]+R[ver])>>1;
					bs[m].push_back(ver);
					if(m<i) flag = true;
				}
			}
			bs[i].clear();
		}
	}
	for(int i=1;i<=N;i++){
		if(answ[i]==-1) printf("NIE\n");
		else printf("%d\n",answ[i]);
	}
}

Compilation message

met.cpp: In function 'int main()':
met.cpp:42: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:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&tmp);
   ~~~~~^~~~~~~~~~~
met.cpp:51:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%lld",&need[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~
met.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&Q);
  ~~~~~^~~~~~~~~
met.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld",&q[i].l,&q[i].r,&q[i].val);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 23936 KB Output is correct
2 Correct 31 ms 23928 KB Output is correct
3 Correct 29 ms 23808 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 23928 KB Output is correct
2 Correct 39 ms 23824 KB Output is correct
3 Correct 37 ms 23936 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 25512 KB Output is correct
2 Correct 416 ms 27768 KB Output is correct
3 Correct 443 ms 27088 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 424 ms 26516 KB Output is correct
2 Correct 374 ms 26668 KB Output is correct
3 Correct 468 ms 27848 KB Output is correct
4 Correct 86 ms 25848 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 25868 KB Output is correct
2 Correct 356 ms 28284 KB Output is correct
3 Correct 183 ms 24844 KB Output is correct
4 Correct 422 ms 27636 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 25164 KB Output is correct
2 Correct 388 ms 26616 KB Output is correct
3 Correct 322 ms 25556 KB Output is correct
4 Correct 498 ms 28940 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2603 ms 42752 KB Output is correct
2 Correct 1460 ms 29936 KB Output is correct
3 Correct 864 ms 27988 KB Output is correct
4 Runtime error 5389 ms 66560 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2940 ms 41584 KB Output is correct
2 Correct 927 ms 29928 KB Output is correct
3 Correct 735 ms 27260 KB Output is correct
4 Runtime error 4400 ms 66560 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)