oj.uz

답안 #102730

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102730 2019-03-27T09:44:50 Z bakpark Meteors (POI11_met) C++14
74 / 100
 4161 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[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;
				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

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 30200 KB Output is correct
2 Correct 45 ms 30200 KB Output is correct
3 Correct 46 ms 30200 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 55 ms 30208 KB Output is correct
2 Correct 49 ms 30200 KB Output is correct
3 Correct 47 ms 30200 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 327 ms 31608 KB Output is correct
2 Correct 426 ms 33912 KB Output is correct
3 Correct 438 ms 33528 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 425 ms 32832 KB Output is correct
2 Correct 407 ms 32760 KB Output is correct
3 Correct 517 ms 34040 KB Output is correct
4 Correct 144 ms 31992 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 197 ms 32260 KB Output is correct
2 Correct 354 ms 34472 KB Output is correct
3 Correct 220 ms 31096 KB Output is correct
4 Correct 411 ms 33912 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 461 ms 31480 KB Output is correct
2 Correct 395 ms 32888 KB Output is correct
3 Correct 329 ms 31716 KB Output is correct
4 Correct 473 ms 35320 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2683 ms 49020 KB Output is correct
2 Correct 1530 ms 36080 KB Output is correct
3 Correct 841 ms 36728 KB Output is correct
4 Runtime error 4161 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2970 ms 47756 KB Output is correct
2 Correct 1027 ms 36308 KB Output is correct
3 Correct 884 ms 36960 KB Output is correct
4 Runtime error 3316 ms 66560 KB Execution killed with signal 9 (could be triggered by violating memory limits)