oj.uz

Submission #102729

# Submission time Handle Problem Language Result Execution time Memory
102729 2019-03-27T09:38:27 Z bakpark Meteors (POI11_met) C++14
74 / 100
 2995 ms 49316 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[2000000];
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;
				for(int pos:arr[ver]){
					sum+=get(pos);
				}
				if(sum>=need[ver]){
					R[ver] = i-1;
					answ[ver] = i;
				}
				else 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 53 ms 30208 KB Output is correct
2 Correct 55 ms 30208 KB Output is correct
3 Correct 54 ms 30184 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 30204 KB Output is correct
2 Correct 54 ms 30080 KB Output is correct
3 Correct 52 ms 30208 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 31964 KB Output is correct
2 Correct 409 ms 34168 KB Output is correct
3 Correct 429 ms 33596 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 33100 KB Output is correct
2 Correct 402 ms 33160 KB Output is correct
3 Correct 486 ms 34256 KB Output is correct
4 Correct 128 ms 32288 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 32376 KB Output is correct
2 Correct 270 ms 34808 KB Output is correct
3 Correct 213 ms 31680 KB Output is correct
4 Correct 399 ms 34044 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 31480 KB Output is correct
2 Correct 407 ms 33264 KB Output is correct
3 Correct 344 ms 31856 KB Output is correct
4 Correct 511 ms 35536 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2676 ms 49316 KB Output is correct
2 Incorrect 1516 ms 36448 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2995 ms 48248 KB Output is correct
2 Incorrect 727 ms 36464 KB Output isn't correct
3 Halted 0 ms 0 KB -