oj.uz

Submission #296914

# Submission time Handle Problem Language Result Execution time Memory
296914 2020-09-11T04:55:21 Z tmwilliamlin168 Wall (IOI14_wall) C++14
0 / 100
 188 ms 14120 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

int stl[1<<22], str[1<<22];

void app(int i, int xl, int xr) {
	stl[i]=min(max(stl[i], xl), xr);
	str[i]=min(max(str[i], xl), xr);
}

void psh(int i) {
	app(2*i, stl[i], str[i]);
	app(2*i+1, stl[i], str[i]);
	stl[i]=0;
	str[i]=1e5;
}

void upd(int l1, int r1, int xl, int xr, int i, int l2, int r2) {
	if(l1<=l2&&r2<=r1) {
		app(i, xl, xr);
		return;
	}
	int m2=(l2+r2)/2;
	psh(i);
	upd(l1, r1, xl, xr, 2*i, l2, m2);
	upd(l1, r1, xl, xr, 2*i+1, m2+1, r2);
}

void bld(int* x, int i, int l2, int r2) {
	if(l2==r2) {
		x[l2]=stl[i];
		return;
	}
	int m2=(l2+r2)/2;
	psh(i);
	bld(x, 2*i, l2, m2);
	bld(x, 2*i+1, m2+1, r2);
}

void buildWall(int n, int k, int* op, int* left, int* right, int* height, int* finalHeight) {
	for(int i=0; i<k; ++i)
		upd(left[i], right[i], k^2?height[i]:0, k^1?height[i]:1e5, 1, 0, n-1);
	bld(finalHeight, 1, 0, n-1);
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 288 KB Output is correct
2 Incorrect 188 ms 14120 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 2 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -