oj.uz

Submission #102727

# Submission time Handle Problem Language Result Execution time Memory
102727 2019-03-27T09:22:09 Z bakpark Meteors (POI11_met) C++14
74 / 100
 2942 ms 50680 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[300001];
quer q[300001];
vector<int> arr[300001];
vector<int> bs[300001];
int L[300001],R[300001],answ[300001];
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 35 ms 24064 KB Output is correct
2 Correct 35 ms 23908 KB Output is correct
3 Correct 31 ms 23928 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 23936 KB Output is correct
2 Correct 36 ms 23936 KB Output is correct
3 Correct 35 ms 23944 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 26364 KB Output is correct
2 Correct 370 ms 28932 KB Output is correct
3 Correct 388 ms 28184 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 27640 KB Output is correct
2 Correct 383 ms 27736 KB Output is correct
3 Correct 462 ms 29048 KB Output is correct
4 Correct 100 ms 26304 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 26744 KB Output is correct
2 Correct 270 ms 29436 KB Output is correct
3 Correct 194 ms 25208 KB Output is correct
4 Correct 404 ms 28920 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 405 ms 26044 KB Output is correct
2 Correct 400 ms 27760 KB Output is correct
3 Correct 376 ms 26488 KB Output is correct
4 Correct 454 ms 30232 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2631 ms 50680 KB Output is correct
2 Incorrect 1585 ms 37744 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2942 ms 49424 KB Output is correct
2 Incorrect 941 ms 36292 KB Output isn't correct
3 Halted 0 ms 0 KB -