oj.uz

Submission #757315

# Submission time Handle Problem Language Result Execution time Memory
757315 2023-06-13T05:06:45 Z SanguineChameleon Pyramid Base (IOI08_pyramid_base) C++17
70 / 100
 5000 ms 94808 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;
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 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);
			}
		}
	}
	for (int i = 1; i <= m * 4; i++) {
		tree[i] = 0;
		lazy[i] = 0;
	}
	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 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.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 39684 KB Output is correct
2 Correct 198 ms 55628 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 53816 KB Output is correct
2 Correct 76 ms 39716 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 24276 KB Output is correct
2 Correct 49 ms 24660 KB Output is correct
3 Correct 43 ms 24688 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 28924 KB Output is correct
2 Correct 254 ms 30308 KB Output is correct
3 Correct 209 ms 30260 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 44748 KB Output is correct
2 Correct 85 ms 29064 KB Output is correct
3 Correct 160 ms 56140 KB Output is correct
4 Correct 512 ms 62560 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 55636 KB Output is correct
2 Correct 954 ms 66068 KB Output is correct
3 Correct 119 ms 42352 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 45920 KB Output is correct
2 Correct 1133 ms 68740 KB Output is correct
3 Correct 1036 ms 68384 KB Output is correct
4 Correct 1092 ms 68544 KB Output is correct
5 Correct 1118 ms 68828 KB Output is correct
6 Correct 59 ms 41704 KB Output is correct

Subtask #13
0 / 10.0

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

Subtask #14
0 / 10.0

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

Subtask #15
0 / 10.0

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