oj.uz

Submission #779239

# Submission time Handle Problem Language Result Execution time Memory
779239 2023-07-11T09:26:06 Z Sohsoh84 Wall (IOI14_wall) C++17
100 / 100
 613 ms 101072 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pll;

#define X		first
#define Y		second

const int MAXN = 1e7 + 10;

pll sg[MAXN];
int n, lz[MAXN], A[MAXN];

inline pll merge(pll a, pll b) {
	a.X = min(a.X, b.X);
	a.Y = max(a.Y, b.Y);
	return a;
}

void build(int l = 0, int r = n - 1, int v = 1) {
	lz[v] = -1;
	if (l == r) sg[v] = {0, 0};
	else {
		int mid = (l + r) >> 1;
		build(l, mid, v << 1);
		build(mid + 1, r, v << 1 | 1);
		sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
	}
}

inline void push(int v) {
	if (lz[v] >= 0) {
		sg[v] = {lz[v], lz[v]};
		if ((v << 1 | 1) < MAXN) lz[v << 1] = lz[v << 1 | 1] = lz[v];
	}

	lz[v] = -1;
}

void q_max(int ql, int qr, int val, int l = 0, int r = n - 1, int v = 1) {
	push(v);
	if (ql > r || qr < l || sg[v].X >= val) return;
	if (ql <= l && qr >= r) {
		if (sg[v].Y <= val) {
			lz[v] = val;
			push(v);
			return;
		}	
	}

	int mid = (l + r) >> 1;
	q_max(ql, qr, val, l, mid, v << 1);
	q_max(ql, qr, val, mid + 1, r, v << 1 | 1);
	sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
	return;
}

void q_min(int ql, int qr, int val, int l = 0, int r = n - 1, int v = 1) {
	push(v);
	if (ql > r || qr < l || sg[v].Y <= val) return;
	if (ql <= l && qr >= r) {
		if (sg[v].X >= val) {
			lz[v] = val;
			push(v);
			return;
		}	
	}

	int mid = (l + r) >> 1;
	q_min(ql, qr, val, l, mid, v << 1);
	q_min(ql, qr, val, mid + 1, r, v << 1 | 1);
	sg[v] = merge(sg[v << 1], sg[v << 1 | 1]);
	return;
}

void print(int l = 0, int r = n - 1, int v = 1) {
	push(v);
	if (l == r) {
		A[l] = sg[v].X;
		return;
	}

	int mid = (l + r) >> 1;
	print(l, mid, v << 1);
	print(mid + 1, r, v << 1 | 1);
}

void buildWall(int n_, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	n = n_;
	build();

	for (int i = 0; i < k; i++) {
		if (op[i] == 1) q_max(left[i], right[i], height[i]);
		else q_min(left[i], right[i], height[i]);
	}

	print();
	for (int i = 0; i < n; i++) finalHeight[i] = A[i];
	return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 452 KB Output is correct
3 Correct 1 ms 360 KB Output is correct
4 Correct 4 ms 1108 KB Output is correct
5 Correct 4 ms 1108 KB Output is correct
6 Correct 4 ms 1108 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 99 ms 13540 KB Output is correct
3 Correct 53 ms 8140 KB Output is correct
4 Correct 143 ms 17300 KB Output is correct
5 Correct 152 ms 15024 KB Output is correct
6 Correct 152 ms 15124 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 468 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 5 ms 1108 KB Output is correct
5 Correct 4 ms 1028 KB Output is correct
6 Correct 4 ms 1108 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 99 ms 9544 KB Output is correct
9 Correct 52 ms 6092 KB Output is correct
10 Correct 131 ms 14420 KB Output is correct
11 Correct 136 ms 15036 KB Output is correct
12 Correct 153 ms 15092 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 103 ms 9492 KB Output is correct
15 Correct 20 ms 2532 KB Output is correct
16 Correct 359 ms 14780 KB Output is correct
17 Correct 217 ms 14824 KB Output is correct
18 Correct 220 ms 14836 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 448 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 1092 KB Output is correct
5 Correct 4 ms 1076 KB Output is correct
6 Correct 4 ms 1108 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 100 ms 9516 KB Output is correct
9 Correct 52 ms 6084 KB Output is correct
10 Correct 131 ms 14440 KB Output is correct
11 Correct 141 ms 14932 KB Output is correct
12 Correct 153 ms 15092 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 109 ms 9532 KB Output is correct
15 Correct 20 ms 2484 KB Output is correct
16 Correct 344 ms 14700 KB Output is correct
17 Correct 233 ms 14816 KB Output is correct
18 Correct 217 ms 14856 KB Output is correct
19 Correct 532 ms 100952 KB Output is correct
20 Correct 533 ms 98620 KB Output is correct
21 Correct 535 ms 101072 KB Output is correct
22 Correct 520 ms 98508 KB Output is correct
23 Correct 559 ms 98524 KB Output is correct
24 Correct 538 ms 98476 KB Output is correct
25 Correct 533 ms 98608 KB Output is correct
26 Correct 535 ms 100940 KB Output is correct
27 Correct 528 ms 100932 KB Output is correct
28 Correct 533 ms 98284 KB Output is correct
29 Correct 547 ms 98324 KB Output is correct
30 Correct 613 ms 98368 KB Output is correct