oj.uz

Submission #667807

# Submission time Handle Problem Language Result Execution time Memory
667807 2022-12-02T05:06:19 Z Baytoro Wall (IOI14_wall) C++17
100 / 100
 542 ms 77388 KB 
#include "bits/stdc++.h"
//#include "grader.cpp"
#include "wall.h"
using namespace std;
//#define int long long
#define fr first
#define sc second
const int INF=1e9+17,mod=1e9+7;
const int N=2e6+5;
pair<int,int> st[4*N]; 
int ans[N];
pair<int,int> f(pair<int,int> a, pair<int,int> b){
	if(a.sc<b.fr)
		return {a.sc,a.sc};
	if(a.fr>b.sc)
		return {a.fr,a.fr};
	return {max(a.fr,b.fr),min(a.sc,b.sc)};
}
void push(int x){
	if(st[x]!=make_pair(-INF,INF)){
		st[2*x]=f(st[x],st[2*x]);
		st[2*x+1]=f(st[x],st[2*x+1]);
		st[x]={-INF,INF};
	}
}
void update(int x, int l, int r, int lx, int rx, pair<int,int> v){
	if(l>rx || r<lx) return;
	if(lx<=l && r<=rx){
		st[x]=f(v,st[x]);
		return;
	}
	if(l!=r) push(x);
	int md=(l+r)/2;
	update(2*x,l,md,lx,rx,v);
	update(2*x+1,md+1,r,lx,rx,v);
}
void get(int x, int l, int r){
	if(l==r){
		ans[l]=st[x].fr;
		return;
	}
	push(x);
	int md=(l+r)/2;
	get(2*x,l,md);
	get(2*x+1,md+1,r);
}
int n,k;
void init(int x=1, int l=0, int r=n-1){
	if(l==0 && r==n-1)
		st[x]={0,0};
	else
		st[x]={-INF,INF};
	if(l==r) return;
	int md=(l+r)/2;
	init(2*x,l,md);
	init(2*x+1,md+1,r);
}
void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
	n=N;
	k=K;
	init();
	for(int i=0;i<k;i++){
		pair<int,int> a={-INF,INF};
		if(op[i]==1)
			a.fr=height[i];
		else
			a.sc=height[i];
		update(1,0,n-1,left[i],right[i],a);
	}
	get(1,0,n-1);
	for(int i=0;i<n;i++)
		finalHeight[i]=ans[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 129 ms 8128 KB Output is correct
3 Correct 131 ms 4260 KB Output is correct
4 Correct 368 ms 11104 KB Output is correct
5 Correct 213 ms 11584 KB Output is correct
6 Correct 201 ms 11672 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 4 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 152 ms 8056 KB Output is correct
9 Correct 127 ms 4172 KB Output is correct
10 Correct 342 ms 11204 KB Output is correct
11 Correct 214 ms 11724 KB Output is correct
12 Correct 200 ms 11676 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 135 ms 8272 KB Output is correct
15 Correct 27 ms 1492 KB Output is correct
16 Correct 480 ms 11460 KB Output is correct
17 Correct 210 ms 11340 KB Output is correct
18 Correct 209 ms 11404 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 3 ms 724 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 126 ms 8144 KB Output is correct
9 Correct 134 ms 4180 KB Output is correct
10 Correct 348 ms 11096 KB Output is correct
11 Correct 224 ms 11632 KB Output is correct
12 Correct 203 ms 11608 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 153 ms 8132 KB Output is correct
15 Correct 27 ms 1448 KB Output is correct
16 Correct 472 ms 11352 KB Output is correct
17 Correct 217 ms 11396 KB Output is correct
18 Correct 216 ms 11372 KB Output is correct
19 Correct 520 ms 66840 KB Output is correct
20 Correct 542 ms 74820 KB Output is correct
21 Correct 527 ms 77372 KB Output is correct
22 Correct 518 ms 74832 KB Output is correct
23 Correct 520 ms 74956 KB Output is correct
24 Correct 514 ms 74860 KB Output is correct
25 Correct 521 ms 74836 KB Output is correct
26 Correct 540 ms 77388 KB Output is correct
27 Correct 522 ms 77308 KB Output is correct
28 Correct 519 ms 74736 KB Output is correct
29 Correct 508 ms 74808 KB Output is correct
30 Correct 511 ms 74728 KB Output is correct