답안 #54246 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54246	2018-07-02T22:00:44 Z	baactree	Pyramid Base (IOI08_pyramid_base)	C++17	70 / 100	5000 ms	55052 KB

pyramid_base

#include <bits/stdc++.h>
using namespace std;
int tree[1 << 21];
int v[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) {
		v[node] += val;
		tree[node] += 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] = min(tree[node * 2], tree[node * 2 + 1])+v[node];
}
int n, m, b, p;
vector<tuple<int, int, int> > vec[1000005];
bool possi(int k) {
	memset(tree, 0, sizeof(tree));
	memset(v, 0, sizeof(v));
	for (int i = 1; i <= n; i++) {
		for (auto v : vec[i]) {
			int y1, y2, c;
			tie(y1, y2, c) = v;
			if (c > 0) update(max(1, y1 - k + 1), min(m - k + 1, y2), c, 1, m - k + 1, 1);
		}
		if (i >= k) {
			for (auto v : vec[i - k]) {
				int y1, y2, c;
				tie(y1, y2, c) = v;
				if (c < 0) update(max(1, y1 - k + 1), min(m - k + 1, y2), c, 1, m - k + 1, 1);
			}
		}
		if (i >= k && tree[1] <= b) return true;
	}
	return false;
}
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);
		vec[x1].emplace_back(y1, y2, b ? c : 1);
		vec[x2].emplace_back(y1, y2, b ? -c : -1);
	}
	int le, ri, ans, mid;
	le = 1;
	ri = 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:40: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:43: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

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	40184 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	40320 KB	Output is correct

Subtask #3
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	61 ms	40376 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	50 ms	40480 KB	Output is correct

Subtask #5
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	84 ms	40480 KB	Output is correct

Subtask #6
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	171 ms	40480 KB	Output is correct
2	Correct	247 ms	40604 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	242 ms	40604 KB	Output is correct
2	Correct	184 ms	40604 KB	Output is correct

Subtask #8
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	89 ms	40652 KB	Output is correct
2	Correct	114 ms	40652 KB	Output is correct
3	Correct	122 ms	40652 KB	Output is correct

Subtask #9
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	204 ms	41292 KB	Output is correct
2	Correct	384 ms	41292 KB	Output is correct
3	Correct	366 ms	41292 KB	Output is correct

Subtask #10
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	395 ms	41676 KB	Output is correct
2	Correct	78 ms	41676 KB	Output is correct
3	Correct	387 ms	41676 KB	Output is correct
4	Correct	511 ms	41836 KB	Output is correct

Subtask #11
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	635 ms	41836 KB	Output is correct
2	Correct	996 ms	41868 KB	Output is correct
3	Correct	300 ms	42036 KB	Output is correct

Subtask #12
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	438 ms	42168 KB	Output is correct
2	Correct	1236 ms	42324 KB	Output is correct
3	Correct	1102 ms	42328 KB	Output is correct
4	Correct	1203 ms	42328 KB	Output is correct
5	Correct	1327 ms	42408 KB	Output is correct
6	Correct	271 ms	42408 KB	Output is correct

Subtask #13
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5040 ms	51128 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #14
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5040 ms	55052 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #15
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	5012 ms	55052 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-