oj.uz

Submission #989930

# Submission time Handle Problem Language Result Execution time Memory
989930 2024-05-29T05:41:35 Z stdfloat Wall (IOI14_wall) C++17
0 / 100
 223 ms 262144 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

vector<int> st;

vector<vector<pair<int, int>>> lz;

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;
		lz[ch].insert(lz[ch].end(), lz[nd].begin(), lz[nd].end());
		lz[ch + 1].insert(lz[ch + 1].end(), lz[nd].begin(), lz[nd].end());
	}

	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].push_back({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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 1204 KB Output is correct
4 Correct 198 ms 189772 KB Output is correct
5 Runtime error 125 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 84 ms 13904 KB Output is correct
3 Runtime error 223 ms 262144 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.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 3 ms 1008 KB Output is correct
4 Correct 193 ms 189904 KB Output is correct
5 Runtime error 127 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

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 3 ms 1116 KB Output is correct
4 Correct 191 ms 189704 KB Output is correct
5 Runtime error 155 ms 262144 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -