oj.uz

Submission #547331

# Submission time Handle Problem Language Result Execution time Memory
547331 2022-04-10T12:22:07 Z sidon Pyramid Base (IOI08_pyramid_base) C++17
70 / 100
 5000 ms 112236 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int Z = 4e5+1;
const ll INF = 1e18;

int sL, sR;
ll sV;
struct SegmentTree {
	int l, r;
	ll v {}, add {};
	SegmentTree *L, *R;
	SegmentTree(int lv, int rv) : l(lv), r(rv) {
		if(r - l > 1) {
			int m = (l + r) / 2;
			L = new SegmentTree(l, m);
			R = new SegmentTree(m, r);
		}
	}
	void rangeAdd(int lv, int rv, ll val) {
		sL = lv, sR = rv + 1, sV = val;
		rangeAdd();
	}
	void rangeAdd() {
		if(sR <= l || r <= sL) return;
		if(sL <= l && r <= sR) {
			add += sV;
			v += sV;
			return;
		}
		L->rangeAdd();
		R->rangeAdd();
		v = min(L->v, R->v) + add;
	}
	void clear() {
		if(r - l > 1) L->clear(), R->clear();
		add = v = 0;
	}
};

int M, N, B, P;
ll C[Z];
array<int, 4> a[Z];

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

	cin >> N >> M >> B >> P;

	for(int i = 0; i < P; ++i) {
		for(int j : {0, 2, 1, 3}) cin >> a[i][j];
		cin >> C[i];
	}
	a[P] = {0, 0, 1, M};
	C[P++] = INF;

	a[P] = {N+1, N+1, 1, M};
	C[P++] = INF;

	int byX[2][P];
	for(int i = 0; i < 2; ++i) {
		iota(byX[i], byX[i] + P, 0);
		sort(byX[i], byX[i] + P, [&](const int &x, const int &y) {
			return a[x][i] < a[y][i];
		});
	}

	SegmentTree* st = new SegmentTree(1, M + 1);

	int x = 0;
	for(int y = 1<<20; y /= 2; ) if(x + y <= min(M, N)) {
		x ^= y;
		bool ok = 0;

		st->rangeAdd(M - x + 2, M, INF);

		for(int i {}, j {}; i < P && !ok; ++i) {
			while(j < P && a[byX[1][j]][1] + x < a[byX[0][i]][0]) {
				int u = byX[1][j++];
				st->rangeAdd(a[u][2] - x + 1, a[u][3], -C[u]);
			}

			if(i && a[byX[0][i-1]][0] != a[byX[0][i]][0]) ok = st->v <= B;

			int u = byX[0][i];
			st->rangeAdd(a[u][2] - x + 1, a[u][3], C[u]);
		}
		st->clear();
		if(!ok) x ^= y;
	}

	cout << x;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1236 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9756 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 354 ms 94236 KB Output is correct
2 Correct 350 ms 94208 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 94288 KB Output is correct
2 Correct 336 ms 94284 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1492 KB Output is correct
2 Correct 45 ms 1492 KB Output is correct
3 Correct 33 ms 1492 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 10652 KB Output is correct
2 Correct 371 ms 10604 KB Output is correct
3 Correct 284 ms 10572 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 702 ms 95464 KB Output is correct
2 Correct 12 ms 1364 KB Output is correct
3 Correct 201 ms 95240 KB Output is correct
4 Correct 874 ms 95512 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1069 ms 95768 KB Output is correct
2 Correct 1387 ms 95864 KB Output is correct
3 Correct 769 ms 95920 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1000 ms 96060 KB Output is correct
2 Correct 1679 ms 96060 KB Output is correct
3 Correct 1641 ms 96076 KB Output is correct
4 Correct 1704 ms 95948 KB Output is correct
5 Correct 1669 ms 96048 KB Output is correct
6 Correct 762 ms 96148 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5032 ms 106292 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 5040 ms 112236 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 220 ms 37328 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -