oj.uz

Submission #881224

# Submission time Handle Problem Language Result Execution time Memory
881224 2023-11-30T22:01:27 Z OAleksa Wall (IOI14_wall) C++14
100 / 100
 700 ms 75956 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;
}

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 2 ms 480 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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 111 ms 10252 KB Output is correct
3 Correct 143 ms 6504 KB Output is correct
4 Correct 345 ms 13220 KB Output is correct
5 Correct 204 ms 13520 KB Output is correct
6 Correct 205 ms 13592 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 2 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 956 KB Output is correct
5 Correct 4 ms 860 KB Output is correct
6 Correct 4 ms 956 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 112 ms 10232 KB Output is correct
9 Correct 126 ms 6388 KB Output is correct
10 Correct 396 ms 13080 KB Output is correct
11 Correct 203 ms 13652 KB Output is correct
12 Correct 205 ms 13432 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 115 ms 10192 KB Output is correct
15 Correct 26 ms 3692 KB Output is correct
16 Correct 446 ms 13396 KB Output is correct
17 Correct 206 ms 13392 KB Output is correct
18 Correct 204 ms 13268 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 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 860 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 10092 KB Output is correct
9 Correct 123 ms 6480 KB Output is correct
10 Correct 373 ms 13076 KB Output is correct
11 Correct 209 ms 13600 KB Output is correct
12 Correct 204 ms 13652 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 113 ms 10160 KB Output is correct
15 Correct 26 ms 3672 KB Output is correct
16 Correct 460 ms 13332 KB Output is correct
17 Correct 207 ms 13300 KB Output is correct
18 Correct 221 ms 13396 KB Output is correct
19 Correct 700 ms 75780 KB Output is correct
20 Correct 659 ms 73172 KB Output is correct
21 Correct 674 ms 75632 KB Output is correct
22 Correct 642 ms 73556 KB Output is correct
23 Correct 638 ms 73296 KB Output is correct
24 Correct 633 ms 73296 KB Output is correct
25 Correct 643 ms 73260 KB Output is correct
26 Correct 649 ms 75956 KB Output is correct
27 Correct 657 ms 75856 KB Output is correct
28 Correct 643 ms 73260 KB Output is correct
29 Correct 641 ms 73116 KB Output is correct
30 Correct 647 ms 73308 KB Output is correct