oj.uz

Submission #757389

# Submission time Handle Problem Language Result Execution time Memory
757389 2023-06-13T06:44:07 Z SanguineChameleon Pyramid Base (IOI08_pyramid_base) C++17
73 / 100
 5000 ms 56040 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;
}
 
const int maxN = 1e6 + 20;
const int maxK = 4e5 + 20;
int tree[maxN << 2];
int lazy[maxN << 2];
int Lx[maxK];
int Ly[maxK];
int Rx[maxK];
int Ry[maxK];
int ly[maxK];
int ry[maxK];
int cnt_x[maxN];
int cnt_y[maxN];
int cost[maxK];
int queries[maxK << 2];
pair<int, int> events_x[maxK << 1];
pair<int, int> events_y[maxK << 1];
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;
	cnt_x[1] = 1;
	cnt_x[n + 1] = 1;
	for (int i = 2; i <= n; i++) {
		cnt_x[i] = 0;
	}
	cnt_y[1] = 1;
	cnt_y[m + 1] = 1;
	for (int i = 2; i <= m; i++) {
		cnt_y[i] = 0;
	}
	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) {
			cnt_x[lx]++;
			cnt_x[rx + 1]++;
			cnt_y[ly]++;
			cnt_y[ry + 1]++;
		}
	}
	int sz_x = 0;
	for (int i = 1; i <= n + 1; i++) {
		swap(sz_x, cnt_x[i]);
		sz_x += cnt_x[i];
	}
	int sz_y = 0;
	for (int i = 1; i <= m + 1; i++) {
		swap(sz_y, cnt_y[i]);
		sz_y += cnt_y[i];
	}
	events_x[cnt_x[1]].first = 1;
	events_x[cnt_x[1]].second = 0;
	cnt_x[1]++;
	events_x[cnt_x[n + 1]].first = n + 1;
	events_x[cnt_x[n + 1]].second = 0;
	cnt_x[n + 1]++;
	events_y[cnt_y[1]].first = 1;
	events_y[cnt_y[1]].second = 0;
	cnt_y[1]++;
	events_y[cnt_y[m + 1]].first = m + 1;
	events_y[cnt_y[m + 1]].second = 0;
	cnt_y[m + 1]++;
	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) {
			events_x[cnt_x[lx]].first = lx;
			events_x[cnt_x[lx]].second = i;
			cnt_x[lx]++;
			events_x[cnt_x[rx + 1]].first = rx + 1;
			events_x[cnt_x[rx + 1]].second = -i;
			cnt_x[rx + 1]++;
			events_y[cnt_y[ly]].first = ly;
			events_y[cnt_y[ly]].second = i;
			cnt_y[ly]++;
			events_y[cnt_y[ry + 1]].first = ry + 1;
			events_y[cnt_y[ry + 1]].second = -i;
			cnt_y[ry + 1]++;
		}
	}
	n = 0;
	int sz_q = 0;
	for (int i = 0; i < sz_x; i++) {
		if (i == 0 || events_x[i].first != events_x[i - 1].first) {
			if (n) {
				queries[sz_q++] = 0;
			}
			n++;
		}
		int id = events_x[i].second;
		if (id) {
			queries[sz_q++] = id;
		}
	}
	n--;
	m = 0;
	for (int i = 0; i < sz_y; 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 = 0; i < sz_q; i++) {
		int id = queries[i];
		if (id > 0) {
			update(1, 1, m, ly[id], ry[id], cost[id]);
		}
		else if (id < 0) {
			update(1, 1, m, ly[-id], ry[-id], -cost[-id]);
		}
		else if (tree[1] <= B) {
			return true;
		}
	}
	return false;
}

const int block = 10000;

void just_do_it() {
	cin >> N >> M >> B >> K;
	int mx = min(N, M);
	for (int i = 1; i <= K; i++) {
		cin >> Lx[i] >> Ly[i] >> Rx[i] >> Ry[i] >> cost[i];
		if (cost[i] > B) {
			int s1 = min(Lx[i] - 1, M);
			int s2 = min(N - Rx[i], M);
			int s3 = min(N, Ly[i] - 1);
			int s4 = min(N, M - Ry[i]);
			mx = min(mx, max(max(max(s1, s2), s3), s4));
		}
	}
	int res = 0;
	while (true) {
		int lt = res + 1;
		int rt = min(mx, lt + block);
		int tmp = rt;
		bool found = false;
		while (lt <= rt) {
			int mt = (lt + rt) >> 1;
			if (check(mt)) {
				res = mt;
				lt = mt + 1;
				found = true;
			}
			else {
				rt = mt - 1;
			}
		}
		if (!found || res < tmp) {
			break;
		}
	}
	cout << res;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 580 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1264 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1200 ms 8292 KB Output is correct
2 Correct 31 ms 8276 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 8408 KB Output is correct
2 Correct 1196 ms 8292 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 852 KB Output is correct
2 Correct 33 ms 984 KB Output is correct
3 Correct 27 ms 980 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 2772 KB Output is correct
2 Correct 132 ms 2800 KB Output is correct
3 Correct 116 ms 2776 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3779 ms 10720 KB Output is correct
2 Correct 26 ms 5824 KB Output is correct
3 Correct 65 ms 6612 KB Output is correct
4 Correct 1006 ms 10704 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3598 ms 11072 KB Output is correct
2 Correct 255 ms 11084 KB Output is correct
3 Correct 4821 ms 11072 KB Output is correct

Subtask #12
0 / 7.0

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

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2303 ms 30976 KB Output is correct
2 Correct 2990 ms 20888 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2519 ms 38100 KB Output is correct
2 Correct 3105 ms 38264 KB Output is correct
3 Execution timed out 5021 ms 33576 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4375 ms 53296 KB Output is correct
2 Execution timed out 5047 ms 56040 KB Time limit exceeded
3 Halted 0 ms 0 KB -