제출 #757427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757427		SanguineChameleon	Pyramid Base (IOI08_pyramid_base)	C++17	70 / 100	1144 ms	53972 KiB

pyramid_base

#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 sub12 {
	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;
	}
}

void just_do_it() {
	int N, M, B, K;
	cin >> N >> M >> B >> K;
	if (B > 0 || K <= 1000) {
		sub12::N = N;
		sub12::M = M;
		sub12::B = B;
		sub12::K = K;
		sub12::solve();
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 0 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10