oj.uz

Submission #126526

# Submission time Handle Problem Language Result Execution time Memory
126526 2019-07-08T03:17:04 Z Boxworld Wall (IOI14_wall) C++14
100 / 100
 775 ms 98440 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
const int maxN=2000100;
int L,R,H,C;
int Mx[maxN*4],Mi[maxN*4],fH[maxN];
inline int ls(int p){return p*2+1;}
inline int rs(int p){return p*2+2;}
void Max(int p,int k){
	if (Mx[p]<k)Mx[p]=k;
	if (Mi[p]<k)Mi[p]=k;
}
void Min(int p,int k){
	if (Mx[p]>k)Mx[p]=k;
	if (Mi[p]>k)Mi[p]=k;
}
void push_node(int p){
	Max(ls(p),Mx[p]);
	Min(ls(p),Mi[p]);
	Max(rs(p),Mx[p]);
	Min(rs(p),Mi[p]);
	Mx[p]=0;
	Mi[p]=0x7fffffff;
}
void update(int p,int l,int r){
	if (L<=l&&r<=R){
		if (C==1)Max(p,H);
		else Min(p,H);
		return;
	}
	push_node(p);
	int m=(l+r)/2;
	if (L<=m)update(ls(p),l,m);
	if (m<R)update(rs(p),m+1,r);
	return;
}
void query(int p,int l,int r){
	if(l==r){fH[l]=Mx[p];return;}
	int m=(l+r)/2;
	push_node(p);
	query(ls(p),l,m);
	query(rs(p),m+1,r);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	memset(Mx,0,sizeof(Mx));
	memset(Mi,0x7f,sizeof(Mi));
	for (int i=0;i<k;i++){
		L=left[i];
		R=right[i];
		H=height[i];
		C=op[i];
		update(0,0,n-1);
	}
	query(0,0,n-1);
	for (int i=0;i<n;i++)finalHeight[i]=fH[i];
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 62968 KB Output is correct
2 Correct 56 ms 63096 KB Output is correct
3 Correct 55 ms 63092 KB Output is correct
4 Correct 62 ms 63228 KB Output is correct
5 Correct 66 ms 63304 KB Output is correct
6 Correct 58 ms 63224 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 62876 KB Output is correct
2 Correct 226 ms 71404 KB Output is correct
3 Correct 276 ms 67064 KB Output is correct
4 Correct 669 ms 72312 KB Output is correct
5 Correct 458 ms 73152 KB Output is correct
6 Correct 360 ms 73208 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 62968 KB Output is correct
2 Correct 55 ms 63096 KB Output is correct
3 Correct 54 ms 62968 KB Output is correct
4 Correct 60 ms 63224 KB Output is correct
5 Correct 58 ms 63224 KB Output is correct
6 Correct 58 ms 63224 KB Output is correct
7 Correct 53 ms 62968 KB Output is correct
8 Correct 229 ms 72516 KB Output is correct
9 Correct 275 ms 68172 KB Output is correct
10 Correct 674 ms 73436 KB Output is correct
11 Correct 380 ms 74276 KB Output is correct
12 Correct 361 ms 74212 KB Output is correct
13 Correct 53 ms 62940 KB Output is correct
14 Correct 231 ms 72836 KB Output is correct
15 Correct 91 ms 64236 KB Output is correct
16 Correct 753 ms 73960 KB Output is correct
17 Correct 386 ms 73928 KB Output is correct
18 Correct 371 ms 73976 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 62964 KB Output is correct
2 Correct 56 ms 63024 KB Output is correct
3 Correct 55 ms 63140 KB Output is correct
4 Correct 62 ms 63228 KB Output is correct
5 Correct 58 ms 63224 KB Output is correct
6 Correct 58 ms 63192 KB Output is correct
7 Correct 54 ms 62940 KB Output is correct
8 Correct 227 ms 72528 KB Output is correct
9 Correct 273 ms 68164 KB Output is correct
10 Correct 675 ms 73376 KB Output is correct
11 Correct 389 ms 74224 KB Output is correct
12 Correct 360 ms 74304 KB Output is correct
13 Correct 54 ms 62872 KB Output is correct
14 Correct 232 ms 72800 KB Output is correct
15 Correct 92 ms 64168 KB Output is correct
16 Correct 747 ms 73972 KB Output is correct
17 Correct 376 ms 73976 KB Output is correct
18 Correct 373 ms 74056 KB Output is correct
19 Correct 773 ms 98440 KB Output is correct
20 Correct 766 ms 95672 KB Output is correct
21 Correct 765 ms 98240 KB Output is correct
22 Correct 765 ms 95864 KB Output is correct
23 Correct 775 ms 95788 KB Output is correct
24 Correct 764 ms 95848 KB Output is correct
25 Correct 766 ms 95864 KB Output is correct
26 Correct 766 ms 98424 KB Output is correct
27 Correct 768 ms 98296 KB Output is correct
28 Correct 770 ms 95728 KB Output is correct
29 Correct 767 ms 95680 KB Output is correct
30 Correct 764 ms 95864 KB Output is correct