oj.uz

Submission #108110

# Submission time Handle Problem Language Result Execution time Memory
108110 2019-04-27T13:25:00 Z hugo_pm Wall (IOI14_wall) C++17
100 / 100
 1306 ms 92208 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const int BIG = (int)(1e9);

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int borne = 2*1000*1000 + 5;
int down[4*borne];
int up[4*borne];
int rep[borne];

void takeDown(int nod, int liv, int riv, int lop, int rop, int val);
void takeUp(int nod, int liv, int riv, int lop, int rop, int val);

void push(int nod, int liv, int riv)
{
	int mm =(liv+riv) / 2;
	takeDown(2*nod, liv, mm, liv, mm, down[nod]);
	takeUp(2*nod, liv, mm, liv, mm, up[nod]);

	takeDown(2*nod+1, mm+1, riv, mm+1, riv, down[nod]);
	takeUp(2*nod+1, mm+1, riv, mm+1, riv, up[nod]);

	down[nod] = BIG;
	up[nod] = 0;
}

void takeDown(int nod, int liv, int riv, int lop, int rop, int val)
{
	if (lop <= liv && riv <= rop) {
		chmin(down[nod], val);
		chmin(up[nod], down[nod]);
		return;
	}
	if (lop > riv || rop < liv) return;
	push(nod,liv,riv);
	int mm = (liv+riv) / 2;
	takeDown(2*nod, liv, mm, lop, rop, val);
	takeDown(2*nod + 1, mm+1, riv, lop, rop, val);
}

void takeUp(int nod, int liv, int riv, int lop, int rop, int val)
{
	if (lop <= liv && riv <= rop) {
		chmax(up[nod], val);
		chmax(down[nod], up[nod]);
		return;
	}
	if (lop > riv || rop < liv) return;
	push(nod,liv,riv);
	int mm = (liv+riv) / 2;
	takeUp(2*nod, liv, mm, lop, rop, val);
	takeUp(2*nod + 1, mm+1, riv, lop, rop, val);
}

void con(int nod, int liv, int riv)
{
	if (liv == riv) {
		rep[liv] = min(down[nod], up[nod]);
		return;
	}
	push(nod,liv,riv);
	int mm = (liv+riv) / 2;
	con(2*nod, liv, mm);
	con(2*nod+1, mm+1, riv);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	form(i, 4*borne) down[i] = BIG;
	form(i, k) {
		if (op[i] == 1) takeUp(1, 0, n-1, left[i], right[i], height[i]);
		else takeDown(1, 0, n-1, left[i], right[i], height[i]);
	}
	con(1, 0, n-1);
	form(i, n) finalHeight[i] = rep[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 31608 KB Output is correct
2 Correct 36 ms 31864 KB Output is correct
3 Correct 30 ms 31744 KB Output is correct
4 Correct 40 ms 32120 KB Output is correct
5 Correct 34 ms 32120 KB Output is correct
6 Correct 39 ms 32120 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31736 KB Output is correct
2 Correct 182 ms 45276 KB Output is correct
3 Correct 343 ms 39160 KB Output is correct
4 Correct 988 ms 51104 KB Output is correct
5 Correct 520 ms 52248 KB Output is correct
6 Correct 544 ms 50680 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 31608 KB Output is correct
2 Correct 28 ms 31740 KB Output is correct
3 Correct 28 ms 31640 KB Output is correct
4 Correct 35 ms 32056 KB Output is correct
5 Correct 36 ms 32084 KB Output is correct
6 Correct 38 ms 32128 KB Output is correct
7 Correct 27 ms 31608 KB Output is correct
8 Correct 184 ms 45320 KB Output is correct
9 Correct 296 ms 39160 KB Output is correct
10 Correct 949 ms 51128 KB Output is correct
11 Correct 448 ms 52216 KB Output is correct
12 Correct 475 ms 50636 KB Output is correct
13 Correct 27 ms 31608 KB Output is correct
14 Correct 199 ms 45304 KB Output is correct
15 Correct 87 ms 33148 KB Output is correct
16 Correct 903 ms 51404 KB Output is correct
17 Correct 450 ms 50936 KB Output is correct
18 Correct 529 ms 50908 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 31608 KB Output is correct
2 Correct 30 ms 31872 KB Output is correct
3 Correct 27 ms 31736 KB Output is correct
4 Correct 35 ms 32120 KB Output is correct
5 Correct 38 ms 32120 KB Output is correct
6 Correct 40 ms 32004 KB Output is correct
7 Correct 29 ms 31608 KB Output is correct
8 Correct 220 ms 45404 KB Output is correct
9 Correct 303 ms 39288 KB Output is correct
10 Correct 1031 ms 51164 KB Output is correct
11 Correct 527 ms 52188 KB Output is correct
12 Correct 521 ms 50680 KB Output is correct
13 Correct 29 ms 31608 KB Output is correct
14 Correct 232 ms 45356 KB Output is correct
15 Correct 77 ms 33272 KB Output is correct
16 Correct 1008 ms 51360 KB Output is correct
17 Correct 531 ms 50808 KB Output is correct
18 Correct 545 ms 50936 KB Output is correct
19 Correct 1306 ms 92144 KB Output is correct
20 Correct 1008 ms 89716 KB Output is correct
21 Correct 1032 ms 92176 KB Output is correct
22 Correct 1231 ms 89692 KB Output is correct
23 Correct 1093 ms 89720 KB Output is correct
24 Correct 1190 ms 89852 KB Output is correct
25 Correct 1016 ms 89668 KB Output is correct
26 Correct 1088 ms 92208 KB Output is correct
27 Correct 1087 ms 92148 KB Output is correct
28 Correct 1054 ms 89720 KB Output is correct
29 Correct 1055 ms 89848 KB Output is correct
30 Correct 1109 ms 89756 KB Output is correct