oj.uz

Submission #751315

# Submission time Handle Problem Language Result Execution time Memory
751315 2023-05-31T11:28:32 Z ZeroCool Wall (IOI14_wall) C++14
61 / 100
 430 ms 26876 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[mxn];

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 440 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 852 KB Output is correct
5 Correct 5 ms 772 KB Output is correct
6 Correct 5 ms 844 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 156 ms 13928 KB Output is correct
3 Correct 147 ms 8044 KB Output is correct
4 Correct 419 ms 20700 KB Output is correct
5 Correct 266 ms 21852 KB Output is correct
6 Correct 322 ms 20316 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 452 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 4 ms 832 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 170 ms 13900 KB Output is correct
9 Correct 152 ms 8084 KB Output is correct
10 Correct 430 ms 20720 KB Output is correct
11 Correct 260 ms 21784 KB Output is correct
12 Correct 261 ms 20240 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 142 ms 13924 KB Output is correct
15 Correct 22 ms 2004 KB Output is correct
16 Correct 385 ms 20980 KB Output is correct
17 Correct 253 ms 20436 KB Output is correct
18 Correct 280 ms 20464 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 876 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 832 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 154 ms 13884 KB Output is correct
9 Correct 145 ms 8056 KB Output is correct
10 Correct 387 ms 20708 KB Output is correct
11 Correct 297 ms 21788 KB Output is correct
12 Correct 258 ms 20280 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 141 ms 13996 KB Output is correct
15 Correct 24 ms 2068 KB Output is correct
16 Correct 392 ms 21100 KB Output is correct
17 Correct 266 ms 20400 KB Output is correct
18 Correct 276 ms 20420 KB Output is correct
19 Runtime error 170 ms 26876 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -