oj.uz

Submission #1009949

# Submission time Handle Problem Language Result Execution time Memory
1009949 2024-06-28T08:13:40 Z stdfloat Wall (IOI14_wall) C++17
61 / 100
 1301 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((nd << 1) + 1, l, (l + r) >> 1, x, y, op, h), upd((nd << 1) + 2, 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);
}

Compilation message

wall.cpp: In function 'int upd(int, int, int, int, int, int, int)':
wall.cpp:55:6: warning: unused variable 'ch' [-Wunused-variable]
   55 |  int ch = (nd << 1) + 1, md = (l + r) >> 1;
      |      ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 12 ms 2140 KB Output is correct
5 Correct 7 ms 2332 KB Output is correct
6 Correct 7 ms 2140 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 74 ms 8256 KB Output is correct
3 Correct 265 ms 6940 KB Output is correct
4 Correct 837 ms 25936 KB Output is correct
5 Correct 251 ms 26448 KB Output is correct
6 Correct 253 ms 26864 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 14 ms 2140 KB Output is correct
5 Correct 8 ms 2140 KB Output is correct
6 Correct 7 ms 2276 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 79 ms 8224 KB Output is correct
9 Correct 291 ms 6996 KB Output is correct
10 Correct 881 ms 26000 KB Output is correct
11 Correct 234 ms 26708 KB Output is correct
12 Correct 231 ms 26452 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 83 ms 8020 KB Output is correct
15 Correct 63 ms 3924 KB Output is correct
16 Correct 1293 ms 26248 KB Output is correct
17 Correct 265 ms 26192 KB Output is correct
18 Correct 254 ms 26192 KB Output is correct

Subtask #4
0 / 39.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 348 KB Output is correct
4 Correct 16 ms 2240 KB Output is correct
5 Correct 7 ms 2144 KB Output is correct
6 Correct 7 ms 2192 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 81 ms 8096 KB Output is correct
9 Correct 262 ms 6760 KB Output is correct
10 Correct 832 ms 26032 KB Output is correct
11 Correct 255 ms 26380 KB Output is correct
12 Correct 236 ms 26448 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 72 ms 8020 KB Output is correct
15 Correct 70 ms 3920 KB Output is correct
16 Correct 1301 ms 26192 KB Output is correct
17 Correct 263 ms 26448 KB Output is correct
18 Correct 254 ms 26192 KB Output is correct
19 Runtime error 496 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -