oj.uz

Submission #881222

# Submission time Handle Problem Language Result Execution time Memory
881222 2023-11-30T21:57:26 Z OAleksa Wall (IOI14_wall) C++14
100 / 100
 703 ms 81296 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 2396 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 904 KB Output is correct
5 Correct 4 ms 856 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 2648 KB Output is correct
2 Correct 114 ms 13164 KB Output is correct
3 Correct 126 ms 8584 KB Output is correct
4 Correct 352 ms 18200 KB Output is correct
5 Correct 209 ms 18932 KB Output is correct
6 Correct 202 ms 18168 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1056 KB Output is correct
5 Correct 4 ms 856 KB Output is correct
6 Correct 4 ms 900 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 115 ms 13184 KB Output is correct
9 Correct 125 ms 8552 KB Output is correct
10 Correct 355 ms 18108 KB Output is correct
11 Correct 210 ms 18812 KB Output is correct
12 Correct 204 ms 18436 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 115 ms 13276 KB Output is correct
15 Correct 25 ms 4188 KB Output is correct
16 Correct 460 ms 18532 KB Output is correct
17 Correct 217 ms 18056 KB Output is correct
18 Correct 218 ms 18056 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 4 ms 856 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 109 ms 13288 KB Output is correct
9 Correct 124 ms 8528 KB Output is correct
10 Correct 347 ms 18200 KB Output is correct
11 Correct 220 ms 18964 KB Output is correct
12 Correct 198 ms 18148 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 123 ms 13288 KB Output is correct
15 Correct 26 ms 4188 KB Output is correct
16 Correct 440 ms 18464 KB Output is correct
17 Correct 207 ms 18056 KB Output is correct
18 Correct 209 ms 18260 KB Output is correct
19 Correct 650 ms 81204 KB Output is correct
20 Correct 668 ms 78624 KB Output is correct
21 Correct 650 ms 81232 KB Output is correct
22 Correct 648 ms 78852 KB Output is correct
23 Correct 665 ms 78632 KB Output is correct
24 Correct 637 ms 78676 KB Output is correct
25 Correct 668 ms 78528 KB Output is correct
26 Correct 703 ms 81296 KB Output is correct
27 Correct 652 ms 81192 KB Output is correct
28 Correct 679 ms 78672 KB Output is correct
29 Correct 641 ms 78544 KB Output is correct
30 Correct 667 ms 78788 KB Output is correct