oj.uz

Submission #18098

# Submission time Handle Problem Language Result Execution time Memory
18098 2016-01-20T07:49:40 Z comet Wall (IOI14_wall) C++
61 / 100
 775 ms 32344 KB 
#include "wall.h"
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

#define LL 2*k+1
#define RR 2*k+2

int lo[2000010],hi[2000010];

void up(int k){
	lo[k]=min(lo[LL],lo[RR]);
	hi[k]=max(hi[LL],hi[RR]);
}

void down(int k){
	lo[LL]=max(lo[LL],lo[k]);
	hi[LL]=max(hi[LL],lo[LL]);
	lo[RR]=max(lo[RR],lo[k]);
	hi[RR]=max(hi[RR],lo[RR]);

	hi[LL]=min(hi[LL],hi[k]);
	lo[LL]=min(lo[LL],hi[LL]);
	hi[RR]=min(hi[RR],hi[k]);
	lo[RR]=min(lo[RR],hi[RR]);
}

void update(int s,int e,int L,int R,int D,int c,int k){
	if(e<L||s>R)return;
	if(L<=s&&e<=R){
		if(D==1){
			lo[k]=max(lo[k],c);
			hi[k]=max(hi[k],lo[k]);
		}
		if(D==2){
			hi[k]=min(hi[k],c);
			lo[k]=min(lo[k],hi[k]);
		}
		return;
	}
	down(k);
	int mid=(s+e)/2;
	update(s,mid,L,R,D,c,LL);
	update(mid+1,e,L,R,D,c,RR);
	up(k);
}

int query(int s,int e,int x,int k){
	if(s==e){
		return lo[k];
	}
	down(k);
	int mid=(s+e)/2;
	if(x<=mid)return query(s,mid,x,LL);
	return query(mid+1,e,x,RR);
}

#undef LL
#undef RR

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
	for(int i=0;i<k;i++){
		update(0,n-1,left[i],right[i],op[i],height[i],0);
	}
	for(int i=0;i<n;i++){
		finalHeight[i]=query(0,n-1,i,0);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16708 KB Output is correct
2 Correct 0 ms 16708 KB Output is correct
3 Correct 0 ms 16708 KB Output is correct
4 Correct 9 ms 16708 KB Output is correct
5 Correct 9 ms 16708 KB Output is correct
6 Correct 8 ms 16708 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16708 KB Output is correct
2 Correct 183 ms 24532 KB Output is correct
3 Correct 295 ms 19956 KB Output is correct
4 Correct 775 ms 24924 KB Output is correct
5 Correct 516 ms 24924 KB Output is correct
6 Correct 511 ms 24924 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16708 KB Output is correct
2 Correct 2 ms 16708 KB Output is correct
3 Correct 0 ms 16708 KB Output is correct
4 Correct 5 ms 16708 KB Output is correct
5 Correct 5 ms 16708 KB Output is correct
6 Correct 9 ms 16708 KB Output is correct
7 Correct 0 ms 16708 KB Output is correct
8 Correct 180 ms 24532 KB Output is correct
9 Correct 286 ms 19956 KB Output is correct
10 Correct 757 ms 24924 KB Output is correct
11 Correct 513 ms 24924 KB Output is correct
12 Correct 495 ms 24924 KB Output is correct
13 Correct 0 ms 16708 KB Output is correct
14 Correct 179 ms 24532 KB Output is correct
15 Correct 43 ms 17192 KB Output is correct
16 Correct 765 ms 24924 KB Output is correct
17 Correct 490 ms 24924 KB Output is correct
18 Correct 512 ms 24924 KB Output is correct

Subtask #4
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16708 KB Output is correct
2 Correct 2 ms 16708 KB Output is correct
3 Correct 0 ms 16708 KB Output is correct
4 Correct 9 ms 16708 KB Output is correct
5 Correct 8 ms 16708 KB Output is correct
6 Correct 8 ms 16708 KB Output is correct
7 Correct 0 ms 16708 KB Output is correct
8 Correct 107 ms 24532 KB Output is correct
9 Correct 272 ms 19956 KB Output is correct
10 Correct 755 ms 24924 KB Output is correct
11 Correct 513 ms 24924 KB Output is correct
12 Correct 509 ms 24924 KB Output is correct
13 Correct 0 ms 16708 KB Output is correct
14 Correct 200 ms 24532 KB Output is correct
15 Correct 43 ms 17192 KB Output is correct
16 Correct 692 ms 24924 KB Output is correct
17 Correct 496 ms 24924 KB Output is correct
18 Correct 516 ms 24924 KB Output is correct
19 Runtime error 200 ms 32344 KB SIGSEGV Segmentation fault
20 Halted 0 ms 0 KB -