oj.uz

Submission #881199

# Submission time Handle Problem Language Result Execution time Memory
881199 2023-11-30T20:58:13 Z OAleksa Wall (IOI14_wall) C++14
100 / 100
 689 ms 86356 KB 
#include<bits/stdc++.h>
#include "wall.h"
using namespace std;
//#define int long long
#define f first
#define s second
const int maxn = 2e6 + 69;
const int inf = 1e9 + 69;
int mn[4 * maxn], mx[4 * maxn], lst[4 * maxn];
void push(int v) {
	int ch1 = v * 2, ch2 = v * 2 + 1;
	int a = mx[v], b = mn[v];
	int c = mx[ch1], d = mn[ch1];
	int e = mx[ch2], f = mn[ch2];
	if (a == 0 && b == inf)
		return;
	if (a >= d) 
		mx[ch1] = mn[ch1] = a;
	else if (b <= c)
		mn[ch1] = mx[ch1] = b;
	else {
		mx[ch1] = max(mx[ch1], a);
		mn[ch1] = min(mn[ch1], b);
	}
	if (a >= f) 
		mx[ch2] = mn[ch2] = a;
	else if (b <= e)
		mn[ch2] = mx[ch2] = b;
	else {
		mx[ch2] = max(mx[ch2], a);
		mn[ch2] = min(mn[ch2], b);
	}
	mn[v] = inf;
	mx[v] = 0;
	lst[ch1] = lst[ch2] = lst[v];
}
void updmax(int v, int tl, int tr, int l, int r, int x) {
	if (tl > r || tr < l)
		return;
	else if (tl >= l && tr <= r) {
		if (x > mn[v])
			mn[v] = mx[v] = x;
		else {
			mx[v] = max(mx[v], x);
			mn[v] = min(mn[v], inf);
		}
		lst[v] = 1;
	}
	else {
		push(v);
		int mid = (tl + tr) / 2;
		updmax(v * 2, tl, mid, l, r, x);
		updmax(v * 2 + 1, mid + 1, tr, l, r, x);
	}
}
void updmin(int v, int tl, int tr, int l, int r, int x) {
	if (tl > r || tr < l)
		return;
	else if (tl >= l && tr <= r) {
		if (x < mx[v])
			mx[v] = mn[v] = x;
		else {
			mx[v] = max(mx[v], 0);
			mn[v] = min(mn[v], x);
		}
		lst[v] = 0;
	}
	else {
		push(v);
		int mid = (tl + tr) / 2;
		updmin(v * 2, tl, mid, l, r, x);
		updmin(v * 2 + 1, mid + 1, tr, l, r, x);
	}
}
int get(int v, int tl, int tr, int p) {
	if (tl == tr) {
		if (lst[v])
			return mx[v];
		return mn[v];
	}
	else {
		int mid = (tl + tr) / 2;
		push(v);
		if (p <= mid)
			return get(v * 2, tl, mid, p);
		else
			return get(v * 2 + 1, mid + 1, tr, p);
	}
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  	for (int i = 0;i < k;i++) {
  		left[i]++;
  		right[i]++;
  		if (op[i] == 1)
  			updmax(1, 1, n, left[i], right[i], height[i]);
  		else
  			updmin(1, 1, n, left[i], right[i], height[i]);
	}
  	for (int i = 0;i < n;i++)
  		finalHeight[i] = get(1, 1, n, i + 1);
  	return;
}

// signed main() {
	// ios_base::sync_with_stdio(false);
	// cin.tie(0);
	// cout.tie(0);
   // int tt = 1;
  	// //cin >> tt;
   // while (tt--) {
   	// int n, q;
   	// cin >> n >> q;
   	// int a[q], b[q], c[q], d[q], e[q];
   	// for (int i = 0;i < q;i++)
   		// cin >> a[i] >> b[i] >> c[i] >> d[i];
   	// buildWall(n, q, a, b, c, d, e);
	// }
	// return 0;
// }

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 860 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 112 ms 10316 KB Output is correct
3 Correct 124 ms 6484 KB Output is correct
4 Correct 350 ms 22616 KB Output is correct
5 Correct 214 ms 23580 KB Output is correct
6 Correct 206 ms 22164 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 972 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 111 ms 15904 KB Output is correct
9 Correct 138 ms 10300 KB Output is correct
10 Correct 353 ms 22764 KB Output is correct
11 Correct 207 ms 23744 KB Output is correct
12 Correct 223 ms 22216 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 122 ms 16244 KB Output is correct
15 Correct 26 ms 4188 KB Output is correct
16 Correct 450 ms 22872 KB Output is correct
17 Correct 221 ms 22260 KB Output is correct
18 Correct 211 ms 22372 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 111 ms 15956 KB Output is correct
9 Correct 125 ms 10324 KB Output is correct
10 Correct 358 ms 22708 KB Output is correct
11 Correct 207 ms 23576 KB Output is correct
12 Correct 200 ms 22096 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 123 ms 16240 KB Output is correct
15 Correct 26 ms 4268 KB Output is correct
16 Correct 460 ms 22912 KB Output is correct
17 Correct 212 ms 22252 KB Output is correct
18 Correct 209 ms 22364 KB Output is correct
19 Correct 676 ms 86356 KB Output is correct
20 Correct 661 ms 83704 KB Output is correct
21 Correct 679 ms 86220 KB Output is correct
22 Correct 684 ms 84024 KB Output is correct
23 Correct 650 ms 83528 KB Output is correct
24 Correct 642 ms 83740 KB Output is correct
25 Correct 648 ms 83540 KB Output is correct
26 Correct 666 ms 86276 KB Output is correct
27 Correct 648 ms 86140 KB Output is correct
28 Correct 673 ms 83932 KB Output is correct
29 Correct 689 ms 83524 KB Output is correct
30 Correct 687 ms 83520 KB Output is correct