oj.uz

Submission #757471

# Submission time Handle Problem Language Result Execution time Memory
757471 2023-06-13T08:27:35 Z SanguineChameleon Pyramid Base (IOI08_pyramid_base) C++17
70 / 100
 5000 ms 147896 KB 
#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

namespace sub2 {
	const int maxN = 1e6 + 20;
	int tree[maxN << 2];
	int lazy[maxN << 2];
	int Lx[maxN];
	int Ly[maxN];
	int Rx[maxN];
	int Ry[maxN];
	int cost[maxN];
	vector<int> queries[maxN];
	int N, M, B, K;

	void reset(int id, int lt, int rt) {
		tree[id] = 0;
		lazy[id] = 0;
		if (lt == rt) {
			return;
		}
		int mt = (lt + rt) >> 1;
		reset(id << 1, lt, mt);
		reset(id << 1 | 1, mt + 1, rt);
	}

	void update(int id, int lt, int rt, int ql, int qr, int add) {
		if (lt == ql && rt == qr) {
			tree[id] += add;
			lazy[id] += add;
			return;
		}
		tree[id << 1] += lazy[id];
		lazy[id << 1] += lazy[id];
		tree[id << 1 | 1] += lazy[id];
		lazy[id << 1 | 1] += lazy[id];
		lazy[id] = 0;
		int mt = (lt + rt) >> 1;
		if (qr <= mt) {
			update(id << 1, lt, mt, ql, qr, add);
		}
		else if (ql >= mt + 1) {
			update(id << 1 | 1, mt + 1, rt, ql, qr, add);
		}
		else {
			update(id << 1, lt, mt, ql, mt, add);
			update(id << 1 | 1, mt + 1, rt, mt + 1, qr, add);
		}
		tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
	}

	bool check(int sz) {
		int n = N - sz + 1;
		int m = M - sz + 1;
		for (int i = 1; i <= n; i++) {
			queries[i].clear();
		}
		for (int i = 1; i <= K; i++) {
			int lx = max(1, Lx[i] - sz + 1);
			int rx = min(n, Rx[i]);
			int ly = max(1, Ly[i] - sz + 1);
			int ry = min(m, Ry[i]);
			if (lx <= rx && ly <= ry) {
				queries[lx].push_back(i);
				if (rx < n) {
					queries[rx + 1].push_back(-i);
				}
			}
		}
		reset(1, 1, m);
		for (int i = 1; i <= n; i++) {
			for (auto id: queries[i]) {
				if (id > 0) {
					int lt = max(1, Ly[id] - sz + 1);
					int rt = min(m, Ry[id]);
					update(1, 1, m, lt, rt, cost[id]);
				}
				else {
					int lt = max(1, Ly[-id] - sz + 1);
					int rt = min(m, Ry[-id]);
					update(1, 1, m, lt, rt, -cost[-id]);
				}
			}
			if (tree[1] <= B) {
				return true;
			}
		}
		return false;
	}

	void solve() {
		for (int i = 1; i <= K; i++) {
			cin >> Lx[i] >> Ly[i] >> Rx[i] >> Ry[i] >> cost[i];
		}
		int res = 0;
		int lt = 1;
		int rt = min(N, M);
		while (lt <= rt) {
			int mt = (lt + rt) >> 1;
			if (check(mt)) {
				res = mt;
				lt = mt + 1;
			}
			else {
				rt = mt - 1;
			}
		}
		cout << res;
	}
}

namespace sub13 {
	struct node {
		int len, min_val, best_all, best_pref, best_suf, lazy;

		node() {};

		node(int _len): len(_len), min_val(0), best_all(_len), best_pref(_len), best_suf(_len), lazy(0) {};
	};

	const int maxN = 1e6 + 20;
	vector<pair<int, int>> rem[maxN];
	vector<pair<int, int>> add[maxN];
	node tree[maxN << 2];
	int N, M, B, K;

	node merge(node L, node R) {
		node res;
		res.len = L.len + R.len;
		res.min_val = min(L.min_val, R.min_val);
		res.best_all = 0;
		int sum = 0;
		if (L.min_val == res.min_val) {
			res.best_all = max(res.best_all, L.best_all);
			sum += L.best_suf;
			if (L.best_pref == L.len && R.min_val == res.min_val) {
				res.best_pref = L.len + R.best_pref;
			}
			else {
				res.best_pref = L.best_pref;
			}
		}
		else {
			res.best_pref = 0;
		}
		if (R.min_val == res.min_val) {
			res.best_all = max(res.best_all, R.best_all);
			sum += R.best_pref;
			if (R.best_suf == R.len && L.min_val == res.min_val) {
				res.best_suf = R.len + L.best_suf;
			}
			else {
				res.best_suf = R.best_suf;
			}
		}
		else {
			res.best_suf = 0;
		}
		res.best_all = max(res.best_all, sum);
		res.lazy = 0;
		return res;
	}

	void build(int id, int lt, int rt) {
		tree[id] = node(rt - lt + 1);
		if (lt == rt) {
			return;
		}
		int mt = (lt + rt) >> 1;
		build(id << 1, lt, mt);
		build(id << 1 | 1, mt + 1, rt);
	}

	void update(int id, int lt, int rt, int ql, int qr, int add) {
		if (lt == ql && rt == qr) {
			tree[id].lazy += add;
			tree[id].min_val += add;
			return;
		}
		tree[id << 1].lazy += tree[id].lazy;
		tree[id << 1].min_val += tree[id].lazy;
		tree[id << 1 | 1].lazy += tree[id].lazy;
		tree[id << 1 | 1].min_val += tree[id].lazy;
		tree[id].lazy = 0;
		int mt = (lt + rt) >> 1;
		if (qr <= mt) {
			update(id << 1, lt, mt, ql, qr, add);
		}
		else if (ql >= mt + 1) {
			update(id << 1 | 1, mt + 1, rt, ql, qr, add);
		}
		else {
			update(id << 1, lt, mt, ql, mt, add);
			update(id << 1 | 1, mt + 1, rt, mt + 1, qr, add);
		}
		tree[id] = merge(tree[id << 1], tree[id << 1 | 1]);
	}

	void solve() {
		for (int i = 1; i <= K; i++) {
			int lx, ly, rx, ry, cost;
			cin >> lx >> ly >> rx >> ry >> cost;
			add[lx].emplace_back(ly, ry);
			rem[rx].emplace_back(ly, ry);
		}
		build(1, 1, M);
		int rt = 0;
		int res = 0;
		for (int i = 1; i <= N; i++) {
			while (rt < N) {
				rt++;
				for (auto p: add[rt]) {
					update(1, 1, M, p.first, p.second, 1);
				}
				int best = (tree[1].min_val == 0 ? tree[1].best_all : 0);
				res = max(res, min(rt - i + 1, best));
				if (best < rt - i + 1 && rt > i) {
					for (auto p: add[rt]) {
						update(1, 1, M, p.first, p.second, -1);
					}
					rt--;
					break;
				}
			}
			for (auto p: rem[i]) {
				update(1, 1, M, p.first, p.second, -1);
			}
		}
		cout << res;
	}
}

void just_do_it() {
	int N, M, B, K;
	cin >> N >> M >> B >> K;
	if (B > 0) {
		sub2::N = N;
		sub2::M = M;
		sub2::B = B;
		sub2::K = K;
		sub2::solve();
	}
	else {
		sub13::N = N;
		sub13::M = M;
		sub13::B = B;
		sub13::K = K;
		sub13::solve();
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 70740 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 70796 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 70752 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 71500 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 76876 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5069 ms 119968 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 120076 KB Output is correct
2 Execution timed out 5089 ms 120012 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 71200 KB Output is correct
2 Correct 81 ms 71424 KB Output is correct
3 Correct 76 ms 71468 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 75212 KB Output is correct
2 Correct 314 ms 75720 KB Output is correct
3 Correct 251 ms 75748 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 83824 KB Output is correct
2 Correct 110 ms 75672 KB Output is correct
3 Correct 171 ms 87756 KB Output is correct
4 Correct 591 ms 95960 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 94744 KB Output is correct
2 Correct 959 ms 97448 KB Output is correct
3 Correct 151 ms 81176 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 318 ms 84464 KB Output is correct
2 Correct 1146 ms 100036 KB Output is correct
3 Correct 1076 ms 99676 KB Output is correct
4 Correct 1237 ms 99820 KB Output is correct
5 Correct 1243 ms 100088 KB Output is correct
6 Correct 85 ms 80308 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1433 ms 131404 KB Output is correct
2 Correct 597 ms 83168 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1648 ms 136356 KB Output is correct
2 Execution timed out 5085 ms 132984 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1751 ms 140912 KB Output is correct
2 Correct 1735 ms 138824 KB Output is correct
3 Correct 1845 ms 138772 KB Output is correct
4 Execution timed out 5041 ms 147896 KB Time limit exceeded
5 Halted 0 ms 0 KB -