oj.uz

Submission #1009943

# Submission time Handle Problem Language Result Execution time Memory
1009943 2024-06-28T08:11:41 Z stdfloat Wall (IOI14_wall) C++17
61 / 100
 1520 ms 262144 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

#define ff  first
#define ss  second
#define pii pair<int, int>

vector<int> st;

vector<vector<pii>> lz;

void Lz(int nd, pii p) {
	for (int i = (int)lz[nd].size() - 1; i >= 0; i--)
		if ((lz[nd][i].ff == 1 && p.ff == 1 && lz[nd][i].ss <= p.ss) || (lz[nd][i].ff == 2 && p.ff == 2 && lz[nd][i].ss >= p.ss)) lz[nd].erase(lz[nd].begin() + i);

	for (auto i : lz[nd]) {
		if (i.ff == p.ff) return;
	}

	lz[nd].push_back(p);

	if ((int)lz[nd].size() == 2) {
		if (lz[nd][0].ff == 1) lz[nd][0].ss = min(lz[nd][0].ss, lz[nd][1].ss);
		else lz[nd][0].ss = max(lz[nd][0].ss, lz[nd][1].ss);
	}
}

void LZ(int nd, int l, int r) {
	for (auto [op, h] : lz[nd]) {
		if (op == 1) st[nd] = max(st[nd], h);
		else st[nd] = min(st[nd], h);
	}

	if (l < r) {
		int ch = (nd << 1) + 1;
		for (auto i : lz[nd]) {
			Lz(ch, i); Lz(ch + 1, i);
		}
	}

	lz[nd].clear();
}

int upd(int nd, int l, int r, int x, int y, int op, int h) {
	LZ(nd, l, r);

	if (r < x || y < l) return st[nd];

	if (x <= l && r <= y) {
		Lz(nd, {op, h}); LZ(nd, l, r);
		return st[nd];
	}

	int ch = (nd << 1) + 1, md = (l + r) >> 1;
	return st[nd] = max(upd(ch, l, md, x, y, op, h), upd(ch + 1, md + 1, r, x, y, op, h));
}

int fnd(int nd, int l, int r, int x) {
	LZ(nd, l, r);

	if (r < x || x < l) return 0;

	if (l == r) return st[nd];

	int ch = (nd << 1) + 1, md = (l + r) >> 1;
	return max(fnd(ch, l, md, x), fnd(ch + 1, md + 1, r, x));
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int fh[]) {
	st.assign(n << 2, 0);
	lz.assign(n << 2, {});
	for (int i = 0; i < k; i++) upd(0, 0, n - 1, l[i], r[i], op[i], h[i]);

	for (int i = 0; i < n; i++) fh[i] = fnd(0, 0, n - 1, i);
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 12 ms 2140 KB Output is correct
5 Correct 9 ms 2140 KB Output is correct
6 Correct 7 ms 2136 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 85 ms 8020 KB Output is correct
3 Correct 273 ms 6732 KB Output is correct
4 Correct 913 ms 25988 KB Output is correct
5 Correct 289 ms 26344 KB Output is correct
6 Correct 250 ms 26444 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 13 ms 2304 KB Output is correct
5 Correct 7 ms 2140 KB Output is correct
6 Correct 6 ms 2140 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 76 ms 8024 KB Output is correct
9 Correct 267 ms 6740 KB Output is correct
10 Correct 939 ms 26016 KB Output is correct
11 Correct 244 ms 26452 KB Output is correct
12 Correct 272 ms 26452 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 85 ms 8176 KB Output is correct
15 Correct 75 ms 3924 KB Output is correct
16 Correct 1520 ms 26128 KB Output is correct
17 Correct 265 ms 26192 KB Output is correct
18 Correct 279 ms 26448 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 14 ms 2140 KB Output is correct
5 Correct 7 ms 2288 KB Output is correct
6 Correct 8 ms 2140 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 83 ms 8352 KB Output is correct
9 Correct 312 ms 6868 KB Output is correct
10 Correct 968 ms 25940 KB Output is correct
11 Correct 262 ms 26452 KB Output is correct
12 Correct 258 ms 26448 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 84 ms 8100 KB Output is correct
15 Correct 76 ms 3924 KB Output is correct
16 Correct 1397 ms 26144 KB Output is correct
17 Correct 287 ms 26192 KB Output is correct
18 Correct 258 ms 26196 KB Output is correct
19 Runtime error 478 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -