oj.uz

Submission #54257

# Submission time Handle Problem Language Result Execution time Memory
54257 2018-07-02T22:24:26 Z baactree Pyramid Base (IOI08_pyramid_base) C++17
80 / 100
 5000 ms 85372 KB 
#include <bits/stdc++.h>
using namespace std;
char buf[1 << 17];
int idx, nidx;
static inline char read() {
	if (idx == nidx) {
		nidx = fread(buf, 1, 1 << 17, stdin);
		idx = 0;
	}
	return buf[idx++];
}
static inline int readInt() {
	int sum = 0;
	bool flag = false;
	char now = read();
	while (now == ' ' || now == '\n')
		now = read();
	if (now == '-') {
		flag = true;
		now = read();
	}
	while (now != ' '&&now != '\n') {
		sum *= 10;
		sum += now - '0';
		now = read();
	}
	if (flag)
		return -sum;
	return sum;
}
int tree[1 << 21][2];
void update(int le, int ri, int val, int nodele, int noderi, int node) {
	if (le > noderi || ri < nodele)return;
	if (le <= nodele && noderi <= ri) {
		tree[node][0] += val;
		tree[node][1] += val;
		return;
	}
	int mid = (nodele + noderi) / 2;
	update(le, ri, val, nodele, mid, node * 2);
	update(le, ri, val, mid + 1, noderi, node * 2 + 1);
	tree[node][0] = min(tree[node * 2][0], tree[node * 2 + 1][0]) + tree[node][1];
}
void init(int nodele, int noderi, int node) {
	tree[node][0] = tree[node][1] = 0;
	if (nodele == noderi) return;
	int mid = (nodele + noderi) / 2;
	init(nodele, mid, node * 2);
	init(mid + 1, noderi, node * 2 + 1);
}
int n, m, b, p;
vector<pair<pair<int,int>,int> > in[1000005], out[1000005];
bool possi(int k) {
	init(1, m - k + 1, 1);
	for (int i = 1; i <= n; i++) {
		for (auto &v : in[i]) update(max(1, v.first.first - k + 1), min(m - k + 1, v.first.second), v.second, 1, m - k + 1, 1);
		if (i >= k) for (auto &v : out[i - k]) update(max(1, v.first.first - k + 1), min(m - k + 1, v.first.second), v.second, 1, m - k + 1, 1);
		if (i >= k && tree[1][0] <= b) return true;
	}
	return false;
}
int main() {
	//scanf("%d%d%d%d", &n, &m, &b, &p);
	n = readInt();
	m = readInt();
	b = readInt();
	p = readInt();
	for (int i = 0; i < p; i++) {
		int x1, y1, x2, y2, c;
		//scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
		x1 = readInt();
		y1 = readInt();
		x2 = readInt();
		y2 = readInt();
		c = readInt();
		in[x1].push_back({ {y1, y2}, b ? c : 1 });
		out[x2].push_back({ {y1, y2}, b ? -c : -1 });
	}
	int le, ri, ans, mid;
	le = 1;
	ri = min(n,m);
	ans = 0;
	while (le <= ri) {
		mid = (le + ri) / 2;
		if (possi(mid)) {
			ans = mid;
			le = mid + 1;
		}
		else ri = mid - 1;
	}
	printf("%d\n", ans);
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 55864 KB Output is correct
2 Correct 323 ms 64068 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 64108 KB Output is correct
2 Correct 181 ms 64108 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 64108 KB Output is correct
2 Correct 84 ms 64108 KB Output is correct
3 Correct 75 ms 64108 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 64108 KB Output is correct
2 Correct 321 ms 64108 KB Output is correct
3 Correct 298 ms 64108 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 64108 KB Output is correct
2 Correct 65 ms 64108 KB Output is correct
3 Correct 213 ms 64764 KB Output is correct
4 Correct 613 ms 65276 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 643 ms 65796 KB Output is correct
2 Correct 1068 ms 65796 KB Output is correct
3 Correct 290 ms 65796 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 65796 KB Output is correct
2 Correct 1406 ms 65916 KB Output is correct
3 Correct 1227 ms 65916 KB Output is correct
4 Correct 1349 ms 65916 KB Output is correct
5 Correct 1279 ms 65916 KB Output is correct
6 Correct 222 ms 65916 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4967 ms 75644 KB Output is correct
2 Correct 383 ms 75644 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5023 ms 80508 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 5024 ms 85372 KB Time limit exceeded
2 Halted 0 ms 0 KB -