oj.uz

Submission #54261

# Submission time Handle Problem Language Result Execution time Memory
54261 2018-07-02T23:18:50 Z baactree Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
 1679 ms 104116 KB 
#include <bits/stdc++.h>
using namespace std;
int tree[1 << 21][4];
bool chk[1 << 21];
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 update2(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] = tree[node][2] = tree[node][3] = noderi - nodele + 1;
		tree[node][1] += val;
		if (tree[node][1])tree[node][0] = tree[node][2] = tree[node][3] = 0;
		else if (nodele != noderi) {
			tree[node][0] = max({ tree[node * 2][0],tree[node * 2 + 1][0],tree[node * 2][3] + tree[node * 2 + 1][2] });
			tree[node][2] = max(tree[node * 2][2], chk[node * 2] ? tree[node * 2][0] + tree[node * 2 + 1][2] : 0);
			tree[node][3] = max(tree[node * 2 + 1][3], chk[node * 2 + 1] ? tree[node * 2 + 1][0] + tree[node * 2][3] : 0);
		}
		chk[node] = (tree[node][0] == noderi - nodele + 1);
		return;
	}
	int mid = (nodele + noderi) / 2;
	update2(le, ri, val, nodele, mid, node * 2);
	update2(le, ri, val, mid + 1, noderi, node * 2 + 1);
	if (tree[node][1])tree[node][0] = tree[node][2] = tree[node][3] = 0;
	else {
		tree[node][0] = max({ tree[node * 2][0],tree[node * 2 + 1][0],tree[node * 2][3] + tree[node * 2 + 1][2] });
		tree[node][2] = max(tree[node * 2][2], chk[node * 2] ? tree[node * 2][0] + tree[node * 2 + 1][2] : 0);
		tree[node][3] = max(tree[node * 2 + 1][3], chk[node * 2 + 1] ? tree[node * 2 + 1][0] + tree[node * 2][3] : 0);
	}
	chk[node] = (tree[node][0] == noderi - nodele + 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);
}
void init2(int nodele, int noderi, int node) {
	tree[node][0] = tree[node][2] =	tree[node][3] = noderi - nodele + 1;
	chk[node] = 1;
	if (nodele == noderi)return;
	int mid = (nodele + noderi) / 2;
	init2(nodele, mid, node * 2);
	init2(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) {
	int t = m - k + 1;
	init(1, t, 1);
	for (int i = 1; i <= n; i++) {
		for (auto &v : in[i]) update(max(1, v.first.first - k + 1), min(t, v.first.second), v.second, 1, t, 1);
		if (i >= k) for (auto &v : out[i - k]) update(max(1, v.first.first - k + 1), min(t, v.first.second), v.second, 1, t, 1);
		if (i >= k && tree[1][0] <= b) return true;
	}
	return false;
}
int solve() {
	int ret = 0;
	init2(1, m, 1);
	for (int st = 1, ed = 1; st <= n; st++) {
		while (ed <= n + 1 && ed - st <= tree[1][0]) {
			ret = max(ret, ed - st);
			for (auto &v : in[ed])update2(v.first.first, v.first.second, v.second, 1, m, 1);
			ed++;
		}
		for (auto &v : out[st])update2(v.first.first, v.first.second, v.second, 1, m, 1);
	}
	return ret;
}
int main() {
	scanf("%d%d%d%d", &n, &m, &b, &p);
	for (int i = 0; i < p; i++) {
		int x1, y1, x2, y2, c;
		scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
		in[x1].push_back({ { y1, y2 }, b ? c : 1 });
		out[x2].push_back({ { y1, y2 }, b ? -c : -1 });
	}
	if (!b)return !printf("%d\n", solve());
	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;
}

Compilation message

pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d%d", &n, &m, &b, &p);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
pyramid_base.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 82440 KB Output is correct
2 Correct 87 ms 82488 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 82488 KB Output is correct
2 Correct 80 ms 82488 KB Output is correct
3 Correct 72 ms 82488 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 82488 KB Output is correct
2 Correct 328 ms 82488 KB Output is correct
3 Correct 259 ms 82488 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 82488 KB Output is correct
2 Correct 65 ms 82488 KB Output is correct
3 Correct 249 ms 82488 KB Output is correct
4 Correct 666 ms 82488 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 82488 KB Output is correct
2 Correct 1199 ms 82488 KB Output is correct
3 Correct 390 ms 82488 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 82488 KB Output is correct
2 Correct 1424 ms 82488 KB Output is correct
3 Correct 1349 ms 82488 KB Output is correct
4 Correct 1426 ms 82488 KB Output is correct
5 Correct 1324 ms 82488 KB Output is correct
6 Correct 201 ms 82488 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 93912 KB Output is correct
2 Correct 434 ms 93912 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1014 ms 98988 KB Output is correct
2 Correct 1053 ms 98988 KB Output is correct
3 Correct 712 ms 98988 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1205 ms 104116 KB Output is correct
2 Correct 1595 ms 104116 KB Output is correct
3 Correct 1679 ms 104116 KB Output is correct
4 Correct 1352 ms 104116 KB Output is correct
5 Correct 945 ms 104116 KB Output is correct