oj.uz

Submission #751314

# Submission time Handle Problem Language Result Execution time Memory
751314 2023-05-31T11:28:04 Z ZeroCool Wall (IOI14_wall) C++14
0 / 100
 1 ms 468 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);
		}
	}
	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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -