oj.uz

Submission #547488

# Submission time Handle Problem Language Result Execution time Memory
547488 2022-04-10T21:05:59 Z sidon Pyramid Base (IOI08_pyramid_base) C++17
35 / 100
 1906 ms 144136 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

int sL, sR;
ll sV;
struct ST0 {
	int l, r;
	ll v {}, add {};
	ST0 *L, *R;
	ST0(int lv, int rv) : l(lv), r(rv) {
		if(r - l > 1) {
			int m = (l + r) / 2;
			L = new ST0(l, m);
			R = new ST0(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;
	}
};
struct ST1 {
	int l, r, add {};
	array<int, 3> v;
	ST1 *L, *R;
	ST1(int lv, int rv) : l(lv), r(rv) {
		v = {r - l, r - l, r - l};
		if(r - l > 1) {
			int m = (l + r) / 2;
			L = new ST1(l, m);
			R = new ST1(m, r);
		}
	}
	void pull() {
		if(add || r - l < 2) v = {!add, !add, !add};
		else {
			int m = (l + r) / 2;
			bool lf = L->v[0] == m - l, rf = R->v[0] == r - m;
			v = {max(L->v[1] + R->v[2], max(L->v[0], R->v[0])), L->v[0] + (lf ? R->v[0] : 0), R->v[1] + (rf ? L->v[1] : 0)};
		}
	}
	void rangeAdd(int lv, int rv, int val) {
		sL = lv, sR = rv + 1, sV = val;
		rangeAdd();
	}
	void rangeAdd() {
		if(sR <= l || r <= sL) return;
		if(sL <= l && r <= sR) return add += sV, pull();
		L->rangeAdd();
		R->rangeAdd();
		pull();
	}
};

int M, N, B, P;
vector<array<ll, 3>> a[2][LIM];

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

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

	for(int i = 0; i < P; ++i) {
		array<ll, 5> u;
		for(ll &j : u) cin >> j;
		a[0][u[0]].push_back({u[1], u[3], u[4]});
		a[1][u[2]].push_back({u[1], u[3], u[4]});
	}

	int x = 0;
	if(B) {
		ST0* st = new ST0(1, M + 1);

		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 = 1; i <= N && !ok; ++i) {
				for(const auto &[l, r, v] : a[0][i])
					st->rangeAdd(l - x + 1, r, v);
				if(i < x) continue;
				for(const auto &[l, r, v] : a[1][i-x])
					st->rangeAdd(l - x + 1, r, -v);
				ok = st->v <= B;
			}
			st->clear();
			if(!ok) x ^= y;
		}
	} else {
		// ST1* st = new ST1(1, M + 1);

		// for(int i {}, j {}; i < P; ++i) {
		// 	if(i + 1 == P || get(1, i) != get(1, i+1)) {
		// 		for(; j < P && ((j && get(0, j) == get(0, j-1)) || (st->v[0] < (get(0, j) - get(1, i)))); ++j) {
		// 			x = max(x, st->v[0]);
		// 			int u = byX[0][j];
		// 			st->rangeAdd(a[u][2], a[u][3], 1);
		// 		}
		// 	}
		// 	int u = byX[1][i];
		// 	st->rangeAdd(a[u][2], a[u][3], -1);
		// }
	}

	cout << x;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 47188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 47280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 47292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 47248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 47316 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 47292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 47372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 48572 KB Output is correct
2 Correct 80 ms 48644 KB Output is correct
3 Correct 64 ms 48596 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 57976 KB Output is correct
2 Correct 412 ms 58060 KB Output is correct
3 Correct 311 ms 57952 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 752 ms 143028 KB Output is correct
2 Correct 41 ms 48952 KB Output is correct
3 Correct 215 ms 142900 KB Output is correct
4 Correct 917 ms 143088 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1175 ms 143488 KB Output is correct
2 Correct 1494 ms 143436 KB Output is correct
3 Correct 820 ms 143564 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1114 ms 143952 KB Output is correct
2 Correct 1840 ms 143900 KB Output is correct
3 Correct 1867 ms 143884 KB Output is correct
4 Correct 1877 ms 143800 KB Output is correct
5 Correct 1906 ms 143896 KB Output is correct
6 Correct 892 ms 144136 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 188 ms 65604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 286 ms 74748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 395 ms 84028 KB Output isn't correct
2 Halted 0 ms 0 KB -