oj.uz

Submission #789534

# Submission time Handle Problem Language Result Execution time Memory
789534 2023-07-21T13:17:18 Z OrazB Wall (IOI14_wall) C++14
100 / 100
 868 ms 99424 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pii pair <int, int>
#define ff first
#define ss second

const int N = 3e6;
const int inf = 1e9+7;
int NP, q, t[4*N][2];

void F(int l, int r, int idx){
	if (l != r){
		if (t[idx<<1][1] < t[idx][0]) t[idx<<1][0] = t[idx<<1][1] = t[idx][0];
		else if (t[idx<<1][0] > t[idx][1]) t[idx<<1][0] = t[idx<<1][1] = t[idx][1];
		else{
			t[idx<<1][0] = max(t[idx<<1][0], t[idx][0]);
			t[idx<<1][1] = min(t[idx<<1][1], t[idx][1]);
		}
		if (t[idx<<1|1][1] < t[idx][0]) t[idx<<1|1][0] = t[idx<<1|1][1] = t[idx][0];
		else if (t[idx<<1|1][0] > t[idx][1]) t[idx<<1|1][0] = t[idx<<1|1][1] = t[idx][1];
		else{
			t[idx<<1|1][0] = max(t[idx<<1|1][0], t[idx][0]);
			t[idx<<1|1][1] = min(t[idx<<1|1][1], t[idx][1]);
		}
		t[idx][0] = 0;
		t[idx][1] = inf;
	}
}

void upd(int ind, int tp, int u, int v, int h, int l = 1, int r = NP, int idx = 1){
	F(l, r, idx);
	if (l > v or r < u) return;
	if (u <= l and r <= v){
		if (tp == 1){
			t[idx][0] = max(t[idx][0], h);
			t[idx][1] = max(t[idx][1], h);
		}else{
			t[idx][1] = min(t[idx][1], h);
			t[idx][0] = min(t[idx][0], h);
		} 
		F(l, r, idx);
		// pos[idx] = ind; 
		return;
	}
	int md = (l+r)>>1;
	upd(ind, tp, u, v, h, l, md, idx<<1);
	upd(ind, tp, u, v, h, md+1, r, idx<<1|1);
}

int tap(int index, int l = 1, int r = NP, int idx = 1){
	F(l, r, idx);
	if (l == r) return t[idx][0];
	// t[idx<<1][0] = max(t[idx<<1][0], t[idx][0]);
	// t[idx<<1][1] = min(t[idx<<1][1], t[idx][1]); 
	// t[idx<<1|1][0] = max(t[idx<<1|1][0], t[idx][0]); 
	// t[idx<<1|1][1] = min(t[idx<<1|1][1], t[idx][1]); 
	// if (pos[idx<<1] < pos[idx]){
	// 	t[idx<<1][1] = max(t[idx<<1][1], t[idx<<1][0]);
	// }
	// if (pos[idx<<1|1] < pos[idx]){
	// 	t[idx<<1|1][1] = max(t[idx<<1|1][1], t[idx<<1|1][0]);
	// }
	int md = (l+r)>>1;
	if (index <= md) return tap(index, l, md, idx<<1);
	return tap(index, md+1, r, idx<<1|1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	NP = n;
	for (int i = 1; i <= 4*n; i++) t[i][1] = inf;
	for (int i = 0; i < k; i++){
		upd(i, op[i], left[i]+1, right[i]+1, height[i]);
	}
	for (int i = 0; i < n; i++) finalHeight[i] = tap(i+1);
}

// int main ()
// {
// 	ios::sync_with_stdio(false);
// 	cin.tie(0);
// 	int n, q; 
// 	cin >> n >> q;
// 	for (int i = 1; i <= 4*n; i++) t[i][1] = inf;
// 	while(q--){
// 		int tp, l, r, h;
// 		cin >> tp >> l >> r >> h;
// 		upd(tp, l+1, r+1, h);
// 	}
// 	for (int i = 1; i <= n; i++) cout << tap(i) << " ";
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 320 KB Output is correct
4 Correct 6 ms 828 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 5 ms 852 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 102 ms 8040 KB Output is correct
3 Correct 144 ms 5568 KB Output is correct
4 Correct 389 ms 12908 KB Output is correct
5 Correct 252 ms 13516 KB Output is correct
6 Correct 261 ms 13512 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 1 ms 340 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 6 ms 836 KB Output is correct
5 Correct 5 ms 836 KB Output is correct
6 Correct 5 ms 836 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 112 ms 11240 KB Output is correct
9 Correct 141 ms 7372 KB Output is correct
10 Correct 387 ms 21400 KB Output is correct
11 Correct 251 ms 22460 KB Output is correct
12 Correct 251 ms 20876 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 118 ms 13836 KB Output is correct
15 Correct 29 ms 1936 KB Output is correct
16 Correct 531 ms 21616 KB Output is correct
17 Correct 262 ms 21072 KB Output is correct
18 Correct 260 ms 21072 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 6 ms 824 KB Output is correct
5 Correct 5 ms 764 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 0 ms 308 KB Output is correct
8 Correct 135 ms 11344 KB Output is correct
9 Correct 136 ms 7392 KB Output is correct
10 Correct 397 ms 21580 KB Output is correct
11 Correct 249 ms 22460 KB Output is correct
12 Correct 251 ms 20888 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 111 ms 13912 KB Output is correct
15 Correct 30 ms 2040 KB Output is correct
16 Correct 578 ms 21628 KB Output is correct
17 Correct 260 ms 21088 KB Output is correct
18 Correct 259 ms 21068 KB Output is correct
19 Correct 856 ms 99228 KB Output is correct
20 Correct 812 ms 96812 KB Output is correct
21 Correct 822 ms 99248 KB Output is correct
22 Correct 827 ms 96720 KB Output is correct
23 Correct 830 ms 96772 KB Output is correct
24 Correct 819 ms 96748 KB Output is correct
25 Correct 814 ms 96716 KB Output is correct
26 Correct 868 ms 99260 KB Output is correct
27 Correct 814 ms 99424 KB Output is correct
28 Correct 802 ms 96724 KB Output is correct
29 Correct 824 ms 96844 KB Output is correct
30 Correct 814 ms 96832 KB Output is correct