oj.uz

Submission #413365

# Submission time Handle Problem Language Result Execution time Memory
413365 2021-05-28T14:57:10 Z Antekb Wall (IOI14_wall) C++14
100 / 100
 842 ms 69488 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;

const int N=(1<<21);
const int INF=1e9;
int tl[N+N], tr[N+N];
void prop(int v){
	if(v>=N)return;
	int l=v+v, r=l+1;
	tl[l]=min(max(tl[l], tl[v]), tr[v]);
	tl[r]=min(max(tl[r], tl[v]), tr[v]);
	tr[l]=max(min(tr[l], tr[v]), tl[v]);
	tr[r]=max(min(tr[r], tr[v]), tl[v]);
	tl[v]=-INF;
	tr[v]=INF;
}
void upd1(int v, int L, int R, int l, int r, int c){
	if(L==l && r==R){
		tr[v]=min(tr[v], c);
		tl[v]=min(tl[v], c);
		return;
	}
	prop(v);
	int M=(L+R)>>1;
	if(l<=M)upd1(2*v, L, M, l, min(r, M), c);
	if(r>M)upd1(2*v+1, M+1, R, max(l, M+1), r, c);
	return;
}
void upd2(int v, int L, int R, int l, int r, int c){
	if(L==l && r==R){
		tr[v]=max(tr[v], c);
		tl[v]=max(tl[v], c);
		return;
	}
	prop(v);
	int M=(L+R)>>1;
	if(l<=M)upd2(2*v, L, M, l, min(r, M), c);
	if(r>M)upd2(2*v+1, M+1, R, max(l, M+1), r, c);
	return;
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	for(int i=0; i<N; i++){
		tr[i]=INF;
		tl[i]=-INF;
	}
	for(int i=0; i<k; i++){
		if(op[i]==1)upd2(1, 0, N-1, left[i], right[i], height[i]);
		else upd1(1, 0, N-1, left[i], right[i], height[i]);
	}
	for(int i=1; i<N; i++){
		prop(i);
	}
	for(int i=0; i<n; i++){
		finalHeight[i]=tl[i+N];
	}
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 33092 KB Output is correct
2 Correct 35 ms 33144 KB Output is correct
3 Correct 35 ms 33124 KB Output is correct
4 Correct 37 ms 33332 KB Output is correct
5 Correct 40 ms 33256 KB Output is correct
6 Correct 36 ms 33348 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 33100 KB Output is correct
2 Correct 367 ms 46832 KB Output is correct
3 Correct 214 ms 40260 KB Output is correct
4 Correct 525 ms 51100 KB Output is correct
5 Correct 360 ms 52184 KB Output is correct
6 Correct 363 ms 50596 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 33124 KB Output is correct
2 Correct 36 ms 33240 KB Output is correct
3 Correct 35 ms 33164 KB Output is correct
4 Correct 37 ms 33260 KB Output is correct
5 Correct 37 ms 33348 KB Output is correct
6 Correct 37 ms 33348 KB Output is correct
7 Correct 34 ms 33112 KB Output is correct
8 Correct 366 ms 46788 KB Output is correct
9 Correct 215 ms 40236 KB Output is correct
10 Correct 525 ms 51232 KB Output is correct
11 Correct 371 ms 52156 KB Output is correct
12 Correct 405 ms 50596 KB Output is correct
13 Correct 32 ms 33092 KB Output is correct
14 Correct 367 ms 46792 KB Output is correct
15 Correct 61 ms 34244 KB Output is correct
16 Correct 520 ms 51372 KB Output is correct
17 Correct 358 ms 50764 KB Output is correct
18 Correct 389 ms 50816 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 33092 KB Output is correct
2 Correct 35 ms 33208 KB Output is correct
3 Correct 34 ms 33160 KB Output is correct
4 Correct 39 ms 33380 KB Output is correct
5 Correct 38 ms 33268 KB Output is correct
6 Correct 37 ms 33348 KB Output is correct
7 Correct 34 ms 33100 KB Output is correct
8 Correct 366 ms 46668 KB Output is correct
9 Correct 220 ms 40220 KB Output is correct
10 Correct 575 ms 51100 KB Output is correct
11 Correct 381 ms 52244 KB Output is correct
12 Correct 390 ms 50596 KB Output is correct
13 Correct 32 ms 33092 KB Output is correct
14 Correct 369 ms 46760 KB Output is correct
15 Correct 81 ms 34200 KB Output is correct
16 Correct 527 ms 51448 KB Output is correct
17 Correct 381 ms 50784 KB Output is correct
18 Correct 364 ms 50780 KB Output is correct
19 Correct 804 ms 69488 KB Output is correct
20 Correct 725 ms 66952 KB Output is correct
21 Correct 758 ms 69464 KB Output is correct
22 Correct 775 ms 66920 KB Output is correct
23 Correct 805 ms 66960 KB Output is correct
24 Correct 795 ms 66992 KB Output is correct
25 Correct 767 ms 66924 KB Output is correct
26 Correct 842 ms 69420 KB Output is correct
27 Correct 754 ms 69488 KB Output is correct
28 Correct 764 ms 67008 KB Output is correct
29 Correct 789 ms 66980 KB Output is correct
30 Correct 796 ms 66964 KB Output is correct