oj.uz

답안 #530529

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
530529 2022-02-25T18:00:43 Z Eyed Pyramid Base (IOI08_pyramid_base) C++14
70 / 100
 5000 ms 98548 KB 
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const ll MOD = 1e9 + 7;

int n, m, b, p;
struct rType {
	int y1;
	int y2;
	int c;
	rType(int yy1 = 0, int yy2 = 0, int cc = 0) : y1(yy1), y2(yy2), c(cc) {};
};

vector<rType> addRect[1000005];
vector<rType> subRect[1000005];

int seg[4000020];
int lazy[4000020];
bool mark[4000020];

void build(int v, int tl, int tr) {
	lazy[v] = 0;
	seg[v] = 0;
	mark[v] = false;
	if (tl == tr) return;
	int mid = (tl + tr) / 2;
	build(2 * v, tl, mid);
	build(2 * v + 1, mid + 1, tr);
} void build() { build(1, 0, m - 1); }
void push(int v) {
	if (mark[v]) {
		lazy[2 * v] += lazy[v];
		lazy[2 * v + 1] += lazy[v];
		mark[2 * v] = true;
		mark[2 * v + 1] = true;
		seg[2 * v] += lazy[v];
		seg[2 * v + 1] += lazy[v];
		lazy[v] = 0;
		mark[v] = false;
	}
}
void upd(int v, int tl, int tr, int l, int r, int x) {
	if (l > r) return;
	if (l <= tl && r >= tr) {
		lazy[v] += x;
		seg[v] += x;
		mark[v] = true;
		return;
	}
	push(v);
	int mid = (tl + tr) / 2;
	upd(2 * v, tl, mid, max(l, tl), min(r, mid), x);
	upd(2 * v + 1, mid + 1, tr, max(l, mid + 1), min(r, tr), x);
	seg[v] = min(seg[2 * v], seg[2 * v + 1]);
} void upd(int l, int r, int x) { upd(1, 0, m - 1, l, r, x); }

int qry(int v, int tl, int tr, int l, int r) {
	if (l > r) return 1e9;
	if (l <= tl && r >= tr) return seg[v];
	push(v);
	int mid = (tl + tr) / 2;
	return min(qry(2 * v, tl, mid, max(l, tl), min(r, mid)), qry(2 * v + 1, mid + 1, tr, max(l, mid + 1), min(r, tr)));
} int qry(int l, int r) { return qry(1, 0, m - 1, l, r); }

bool check(int p) {

	build();
	for (int i = 0; i < p; ++i) {
		for (rType r : addRect[i]) {
			upd(max(r.y1, p - 1), min(m - 1, r.y2 + p - 1), r.c);
		}
	}
	if (qry(p - 1, m - 1) <= b) return true;
	for (int i = p; i < n; ++i) {
		for (rType r : addRect[i]) {
			upd(max(r.y1, p - 1), min(m - 1, r.y2 + p - 1), r.c);
		}
		for (rType r : subRect[i - p]) {
			upd(max(r.y1, p - 1), min(m - 1, r.y2 + p - 1), -r.c);
		}
		if (qry(p - 1, m - 1) <= b) return true;
	}
	return false;

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	cin >> b;
	cin >> p;
	for (int i = 0; i < p; ++i) {
		int x1, y1, x2, y2, c;
		cin >> x1 >> y1 >> x2 >> y2 >> c;
		--x1; --y1; --x2; --y2;
		addRect[x1].push_back(rType(y1, y2, c));
		subRect[x2].push_back(rType(y1, y2, c));
	}
	int l = 0;
	int r = min(m, n);
	while (l < r) {
		int mid = (l + r + 1) / 2;
		if (check(mid)) l = mid;
		else r = mid - 1;
	}
	cout << l << endl;

	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 468 ms 65880 KB Output is correct
2 Correct 2373 ms 65832 KB Output is correct

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2027 ms 65844 KB Output is correct
2 Correct 815 ms 65836 KB Output is correct

Subtask #8
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 47932 KB Output is correct
2 Correct 97 ms 47924 KB Output is correct
3 Correct 74 ms 47936 KB Output is correct

Subtask #9
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 210 ms 50744 KB Output is correct
2 Correct 447 ms 50872 KB Output is correct
3 Correct 382 ms 50768 KB Output is correct

Subtask #10
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 756 ms 67568 KB Output is correct
2 Correct 124 ms 48948 KB Output is correct
3 Correct 171 ms 66944 KB Output is correct
4 Correct 1438 ms 67744 KB Output is correct

Subtask #11
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1276 ms 68024 KB Output is correct
2 Correct 3553 ms 67856 KB Output is correct
3 Correct 620 ms 68088 KB Output is correct

Subtask #12
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1020 ms 68476 KB Output is correct
2 Correct 3498 ms 68356 KB Output is correct
3 Correct 3223 ms 68320 KB Output is correct
4 Correct 3808 ms 68424 KB Output is correct
5 Correct 3697 ms 68344 KB Output is correct
6 Correct 457 ms 68576 KB Output is correct

Subtask #13
0 / 10.0

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

Subtask #14
0 / 10.0

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

Subtask #15
0 / 10.0

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