oj.uz

Submission #751316

# Submission time Handle Problem Language Result Execution time Memory
751316 2023-05-31T11:32:01 Z ZeroCool Wall (IOI14_wall) C++14
100 / 100
 638 ms 77388 KB 
#include "wall.h"
#include <bits/stdc++.h>

const int mxn = 2000010;
const int inf = INT_MAX;

using namespace std;

struct Node{
	int mx = 0;
	int mn = 0;
};

int res[mxn];
Node seg[2 * (1<<21) + 20];

void push(int k){
	seg[k * 2].mn = min(seg[k * 2].mn, seg[k].mn);
    seg[k * 2].mn = max(seg[k * 2].mn, seg[k].mx);
    seg[k * 2].mx = min(seg[k * 2].mx, seg[k].mn);
    seg[k * 2].mx = max(seg[k * 2].mx, seg[k].mx);
    seg[k * 2 + 1].mn = min(seg[k * 2 + 1].mn, seg[k].mn);
    seg[k * 2 + 1].mn = max(seg[k * 2 + 1].mn, seg[k].mx);
    seg[k * 2 + 1].mx = min(seg[k * 2 + 1].mx, seg[k].mn);
    seg[k * 2 + 1].mx = max(seg[k * 2 + 1].mx, seg[k].mx);
}

void update(int k,int l,int r,int i,int j,int v,int t){
	if(l > j || r < i)return;
	if(i <= l && r<= j){
		if(t==1){
			seg[k].mn = max(seg[k].mn,v);
			seg[k].mx = max(seg[k].mx,v);
		}else{
			seg[k].mn = min(seg[k].mn,v);
			seg[k].mx = min(seg[k].mx,v);
		}
		return;
	}
	push(k);
	seg[k].mn = 2000010;
    seg[k].mx = 0;
	int mid = (l+r)/2;
	update(k*2,l,mid,i,j,v,t);
	update(k*2+1,mid+1,r,i,j,v,t);
}

void get(int k,int l,int r){
	if(l == r){
		res[l] = seg[k].mn;
		return;
	}
	push(k);
	int mid = (l+r)/2;
	get(k*2,l,mid);
	get(k*2+1,mid+1,r);
}

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

Subtask #1
8.0 / 8.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 4 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 141 ms 8088 KB Output is correct
3 Correct 137 ms 4260 KB Output is correct
4 Correct 390 ms 11180 KB Output is correct
5 Correct 256 ms 11600 KB Output is correct
6 Correct 259 ms 11616 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 5 ms 724 KB Output is correct
6 Correct 4 ms 728 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 149 ms 8088 KB Output is correct
9 Correct 175 ms 4252 KB Output is correct
10 Correct 365 ms 11156 KB Output is correct
11 Correct 267 ms 11684 KB Output is correct
12 Correct 282 ms 11596 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 142 ms 8160 KB Output is correct
15 Correct 23 ms 1444 KB Output is correct
16 Correct 392 ms 11372 KB Output is correct
17 Correct 261 ms 11428 KB Output is correct
18 Correct 262 ms 11340 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 2 ms 340 KB Output is correct
4 Correct 5 ms 724 KB Output is correct
5 Correct 5 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 138 ms 8104 KB Output is correct
9 Correct 137 ms 4304 KB Output is correct
10 Correct 385 ms 11088 KB Output is correct
11 Correct 262 ms 11600 KB Output is correct
12 Correct 255 ms 11668 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 137 ms 8036 KB Output is correct
15 Correct 22 ms 1500 KB Output is correct
16 Correct 373 ms 11336 KB Output is correct
17 Correct 258 ms 11336 KB Output is correct
18 Correct 257 ms 11468 KB Output is correct
19 Correct 600 ms 66868 KB Output is correct
20 Correct 598 ms 74940 KB Output is correct
21 Correct 602 ms 77388 KB Output is correct
22 Correct 612 ms 74856 KB Output is correct
23 Correct 617 ms 74832 KB Output is correct
24 Correct 607 ms 74784 KB Output is correct
25 Correct 638 ms 74840 KB Output is correct
26 Correct 631 ms 77252 KB Output is correct
27 Correct 601 ms 77276 KB Output is correct
28 Correct 630 ms 74784 KB Output is correct
29 Correct 621 ms 74936 KB Output is correct
30 Correct 616 ms 74736 KB Output is correct