oj.uz

Submission #655074

# Submission time Handle Problem Language Result Execution time Memory
655074 2022-11-03T00:19:32 Z thiago_bastos Wall (IOI14_wall) C++17
100 / 100
 1794 ms 79844 KB 
#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

#define INF 1000000000
#define INFLL 1000000000000000000ll
#define EPS 1e-9
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
#define fi first
#define sc second
 
using i64 = long long;
using u64 = unsigned long long;
using ld = long double;
using ii = pair<int, int>;	

const int N = 1 << 22;

struct Item {
	int type;
	int x, y;
};

Item lazy[N];
bool marked[N];

int F(Item i, int x) {
	if(i.type == 0) return max(i.x, min(i.y, x));
	return min(i.x, max(i.y, x));
}

Item A[2][2][4][4][4][4];

Item merge(Item a, Item b) {
	int p[4] = {a.x, a.y, b.x, b.y};

	sort(p, p + 4);

	auto [_, ax, ay] = a;
	auto [__, bx, by] = b;

	ax = lower_bound(p, p + 4, ax) - p;
	ay = lower_bound(p, p + 4, ay) - p;
	bx = lower_bound(p, p + 4, bx) - p;
	by = lower_bound(p, p + 4, by) - p;

	auto k = A[a.type][b.type][ax][ay][bx][by];

	return {k.type, p[k.x], p[k.y]};
}

void build(int l, int r, int k = 1) {
	lazy[k] = {0, 0, INF};
	if(l != r) {
		build(l, (l + r) / 2, 2 * k);
		build((l + r) / 2 + 1, r, 2 * k + 1);
	}
}

void push(int k) {
	if(!marked[k]) return;
	for(int i : {2 * k, 2 * k + 1}) {
		marked[i] = true;
		lazy[i] = merge(lazy[k], lazy[i]);
	}
	lazy[k] = {0, 0, INF};
	marked[k] = false;
}

void upd(int l, int r, Item x, int lo, int hi, int k = 1) {
	if(l > r || lo > hi || r < lo || hi < l) return;
	else if(lo >= l && hi <= r) {
		lazy[k] = merge(x, lazy[k]);
		marked[k] = true;
	} else {
		int m = (lo + hi) / 2;
		push(k);
		upd(l, r, x, lo, m, 2 * k);
		upd(l, r, x, m + 1, hi, 2 * k + 1);
	}
}

int query(int i, int lo, int hi, int k = 1) {
	if(lo == hi) return F(lazy[k], 0);
	int m = (lo + hi) / 2;
	push(k);
	return i <= m ? query(i, lo, m, 2 * k) : query(i, m + 1, hi, 2 * k + 1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	
	build(0, n - 1);

	for(int at : {0,1})
	for(int bt : {0,1})
	for(int ax : {0,1,2,3})
	for(int ay : {0,1,2,3})
	for(int bx : {0,1,2,3})
	for(int by : {0,1,2,3})
	for(int t : {0, 1})
	for(int i : {0,1,2,3})
	for(int j : {0,1,2,3}) {
		bool ok = true;
		for(int x : {0,1,2,3}) ok = ok && F({at, ax, ay}, F({bt, bx, by}, x)) == F({t, i, j}, x);
		if(ok) A[at][bt][ax][ay][bx][by] = {t, i, j};
	}

	for(int i = 0; i < k; ++i) {
		Item v;

		if(op[i] == 1) {
			v.type = 0;
			v.x = height[i];
			v.y = INF;
		} else {
			v.type = 1;
			v.x = height[i];
			v.y = 0;
		}
		
		upd(left[i], right[i], v, 0, n - 1);
	}

	for(int i = 0; i < n; ++i)
		finalHeight[i] = query(i, 0, n - 1);

	return;
}

Subtask #1
8.0 / 8.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 4 ms 340 KB Output is correct
4 Correct 18 ms 864 KB Output is correct
5 Correct 8 ms 852 KB Output is correct
6 Correct 8 ms 840 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 145 ms 8168 KB Output is correct
3 Correct 594 ms 4480 KB Output is correct
4 Correct 1794 ms 12148 KB Output is correct
5 Correct 323 ms 12508 KB Output is correct
6 Correct 309 ms 12592 KB Output is correct

Subtask #3
29.0 / 29.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 4 ms 340 KB Output is correct
4 Correct 17 ms 860 KB Output is correct
5 Correct 8 ms 852 KB Output is correct
6 Correct 8 ms 804 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 145 ms 8268 KB Output is correct
9 Correct 599 ms 4556 KB Output is correct
10 Correct 1773 ms 12136 KB Output is correct
11 Correct 321 ms 12652 KB Output is correct
12 Correct 314 ms 12808 KB Output is correct
13 Correct 2 ms 212 KB Output is correct
14 Correct 157 ms 8232 KB Output is correct
15 Correct 93 ms 1772 KB Output is correct
16 Correct 1748 ms 12456 KB Output is correct
17 Correct 332 ms 12364 KB Output is correct
18 Correct 332 ms 12400 KB Output is correct

Subtask #4
39.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 4 ms 340 KB Output is correct
4 Correct 17 ms 868 KB Output is correct
5 Correct 8 ms 848 KB Output is correct
6 Correct 10 ms 856 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 150 ms 8212 KB Output is correct
9 Correct 584 ms 4504 KB Output is correct
10 Correct 1752 ms 12200 KB Output is correct
11 Correct 328 ms 12680 KB Output is correct
12 Correct 319 ms 12656 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 157 ms 8240 KB Output is correct
15 Correct 94 ms 1780 KB Output is correct
16 Correct 1752 ms 12400 KB Output is correct
17 Correct 323 ms 12400 KB Output is correct
18 Correct 329 ms 12484 KB Output is correct
19 Correct 1331 ms 79704 KB Output is correct
20 Correct 1323 ms 77364 KB Output is correct
21 Correct 1310 ms 79844 KB Output is correct
22 Correct 1347 ms 77140 KB Output is correct
23 Correct 1304 ms 77352 KB Output is correct
24 Correct 1301 ms 77124 KB Output is correct
25 Correct 1316 ms 77220 KB Output is correct
26 Correct 1312 ms 79692 KB Output is correct
27 Correct 1317 ms 79748 KB Output is correct
28 Correct 1328 ms 77316 KB Output is correct
29 Correct 1301 ms 77240 KB Output is correct
30 Correct 1372 ms 77152 KB Output is correct