oj.uz

Submission #655063

# Submission time Handle Problem Language Result Execution time Memory
655063 2022-11-02T23:13:33 Z thiago_bastos Wall (IOI14_wall) C++17
100 / 100
 2287 ms 84976 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 merge(Item a, Item b) {
	int p[4] = {a.x, a.y, b.x, b.y};

	for(int t : {0, 1}) {
		for(int x1 : p) {
			for(int x2 : p) {
				bool ok = true;
				for(int x : p) ok = ok && F(a, F(b, x)) == F({t, x1, x2}, x);
				if(ok) return {t, x1, x2};
			}
		}
	}

	return {0,0,0};
}

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 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 0 ms 304 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 18 ms 980 KB Output is correct
5 Correct 9 ms 932 KB Output is correct
6 Correct 9 ms 912 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 174 ms 13284 KB Output is correct
3 Correct 723 ms 8240 KB Output is correct
4 Correct 2151 ms 17244 KB Output is correct
5 Correct 333 ms 17760 KB Output is correct
6 Correct 322 ms 17752 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 18 ms 924 KB Output is correct
5 Correct 8 ms 936 KB Output is correct
6 Correct 8 ms 984 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 168 ms 13404 KB Output is correct
9 Correct 722 ms 8236 KB Output is correct
10 Correct 2287 ms 17244 KB Output is correct
11 Correct 325 ms 17740 KB Output is correct
12 Correct 317 ms 17788 KB Output is correct
13 Correct 1 ms 312 KB Output is correct
14 Correct 159 ms 13336 KB Output is correct
15 Correct 98 ms 2320 KB Output is correct
16 Correct 1781 ms 17504 KB Output is correct
17 Correct 316 ms 17536 KB Output is correct
18 Correct 304 ms 17504 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 2 ms 340 KB Output is correct
3 Correct 4 ms 340 KB Output is correct
4 Correct 17 ms 936 KB Output is correct
5 Correct 9 ms 980 KB Output is correct
6 Correct 7 ms 980 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 159 ms 13392 KB Output is correct
9 Correct 699 ms 8268 KB Output is correct
10 Correct 2084 ms 17248 KB Output is correct
11 Correct 325 ms 17712 KB Output is correct
12 Correct 317 ms 17756 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 151 ms 13344 KB Output is correct
15 Correct 96 ms 2324 KB Output is correct
16 Correct 1750 ms 17608 KB Output is correct
17 Correct 314 ms 17608 KB Output is correct
18 Correct 307 ms 17508 KB Output is correct
19 Correct 1257 ms 84884 KB Output is correct
20 Correct 1226 ms 82388 KB Output is correct
21 Correct 1227 ms 84976 KB Output is correct
22 Correct 1219 ms 82416 KB Output is correct
23 Correct 1217 ms 82412 KB Output is correct
24 Correct 1241 ms 82460 KB Output is correct
25 Correct 1220 ms 82412 KB Output is correct
26 Correct 1235 ms 84920 KB Output is correct
27 Correct 1223 ms 84940 KB Output is correct
28 Correct 1215 ms 82484 KB Output is correct
29 Correct 1240 ms 82472 KB Output is correct
30 Correct 1222 ms 82484 KB Output is correct