Submission #757329

#	Time	Username	Problem	Language	Result	Execution time	Memory
757329		SanguineChameleon	Pyramid Base (IOI08_pyramid_base)	C++17	80 / 100	5045 ms	96144 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;
}

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 ly[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();
	}
	vector<pair<int, int>> events_x;
	vector<pair<int, int>> events_y;
	events_x.emplace_back(1, 0);
	events_x.emplace_back(n + 1, 0);
	events_y.emplace_back(1, 0);
	events_y.emplace_back(m + 1, 0);
	for (int i = 1; i <= K; i++) {
		int lx = max(1, Lx[i] - sz + 1);
		int rx = min(n, Rx[i]);
		ly[i] = max(1, Ly[i] - sz + 1);
		ry[i] = min(m, Ry[i]);
		if (lx <= rx && ly[i] <= ry[i]) {
			events_x.emplace_back(lx, i);
			events_x.emplace_back(rx + 1, -i);
			events_y.emplace_back(ly[i], i);
			events_y.emplace_back(ry[i] + 1, -i);
		}
	}
	sort(events_x.begin(), events_x.end());
	sort(events_y.begin(), events_y.end());
	n = 0;
	for (int i = 0; i < (int)events_x.size(); i++) {
		if (i == 0 || events_x[i].first != events_x[i - 1].first) {
			queries[++n].clear();
		}
		int id = events_x[i].second;
		if (id) {
			queries[n].push_back(id);
		}
	}
	n--;
	m = 0;
	for (int i = 0; i < (int)events_y.size(); i++) {
		if (i == 0 || events_y[i].first != events_y[i - 1].first) {
			m++;
		}
		int id = events_y[i].second;
		if (id > 0) {
			ly[id] = m;
		}
		else {
			ry[-id] = m - 1;
		}
	}
	m--;
	reset(1, 1, m);
	for (int i = 1; i <= n; i++) {
		for (auto id: queries[i]) {
			if (id > 0) {
				update(1, 1, m, ly[id], ry[id], cost[id]);
			}
			else {
				update(1, 1, m, ly[-id], ry[-id], -cost[-id]);
			}
		}
		if (tree[1] <= B) {
			return true;
		}
	}
	return false;
}

void just_do_it() {
	cin >> N >> M >> B >> K;
	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;
}

• 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: 10 / 10
• Subtask 14: 0 / 10
• Subtask 15: 0 / 10