Submission #1027117

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1027117	2024-07-18T22:14:37 Z	Tob	Pyramid Base (IOI08_pyramid_base)	C++14	100 / 100	839 ms	135748 KB

pyramid_base

#include <bits/stdc++.h>

#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pii;
typedef array <int, 6> nd;

const int K = 4e5 + 7, N = 1e6 + 7, ofs = (1 << 20);

int n, m, b, k;
int co[K][4], c[K];
vector <int> add[N], rem[N];

pii t[2*ofs];
nd t2[2*ofs];

inline pii Merge(pii x, pii y) {return {x.F+y.F, min(x.S, x.F+y.S)};}
inline void update(int x, int val) {
	x += ofs;
	t[x].F += val; t[x].S += val;
	while (x /= 2) t[x] = Merge(t[2*x], t[2*x+1]);
}
inline int get() {return t[1].S;}

void prop(int x) {
	t2[x][3] += t2[x][5];
	if (x < ofs) {t2[2*x][5] += t2[x][5]; t2[2*x+1][5] += t2[x][5];}
	t2[x][5] = 0;
}
inline nd Merge2(nd x, nd y) {
	if (x[3] < y[3]) return {x[0], 0, max(x[2], x[1]), x[3], x[4]+y[4], 0};
	if (x[3] > y[3]) return {0, y[1], max(y[2], y[0]), y[3], x[4]+y[4], 0};
	return {x[0]+y[0]*(x[0]==x[4]), x[1]*(y[1]==y[4])+y[1], max(max(x[2], y[2]), x[1]+y[0]), x[3], x[4]+y[4], 0};
}
inline void Update(int x, int a, int b, int val, int lo = 0, int hi = ofs-1) {
	prop(x);
	if (b < lo || hi < a) return;
	if (a <= lo && hi <= b) {
		t2[x][5] += val;
		prop(x);
		return;
	}
	int mid = (lo + hi) / 2;
	Update(2*x, a, b, val, lo, mid);
	Update(2*x+1, a, b, val, mid+1, hi);
	t2[x] = Merge2(t2[2*x], t2[2*x+1]);
}
inline int Get() {return t2[1][2]*(!t2[1][3]);}

int main () {
	FIO;
	cin >> n >> m >> b >> k;
	
	for (int i = 0; i < k; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> co[i][j]; co[i][j]--;
		}
		cin >> c[i];
	}
	if (b) {
		int lo = 0, hi = min(n, m);
		while (lo < hi) {
			int mid = (lo + hi + 1) / 2;
			for (int i = 0; i < k; i++) {
				add[max(0, co[i][0]-mid+1)].pb(i);
				rem[min(co[i][2], n-mid)].pb(i);
			}
			update(m-mid+1, b+1);
			int mn = b+1;
			for (int i = 0; i <= n-mid; i++) {
				for (auto x : add[i]) {
					update(max(0, co[x][1]-mid+1), c[x]);
					update(co[x][3]+1, -c[x]);
				}
				add[i].clear();
				mn = min(mn, get());
				for (auto x : rem[i]) {
					update(max(0, co[x][1]-mid+1), -c[x]);
					update(co[x][3]+1, c[x]);
				}
				rem[i].clear();
			}
			update(m-mid+1, -b-1);
			if (mn <= b) lo = mid;
			else hi = mid-1;
		}
		
		cout << lo << "\n";
	}
	else {
		for (int i = ofs; i < 2*ofs; i++) t2[i] = {1, 1, 1, (i>=m+ofs), 1, 0};
		for (int i = ofs-1; i; i--) t2[i] = Merge2(t2[2*i], t2[2*i+1]);
		for (int i = 0; i < k; i++) {
			add[co[i][0]].pb(i);
			rem[co[i][2]].pb(i);
		}
		int mx = 0;
		for (int i = 0, j = 0; i < n; i++) {
			for (auto x : add[i]) Update(1, co[x][1], co[x][3], 1);
			while (Get() < i-j+1) {
				mx = max(mx, Get());
				for (auto x : rem[j]) Update(1, co[x][1], co[x][3], -1);
				j++;
			}
			mx = max(mx, i-j+1);
		}
		cout << mx << "\n";
	}

	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	101176 KB	Output is correct
2	Correct	29 ms	101208 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	101208 KB	Output is correct
2	Correct	27 ms	101208 KB	Output is correct

Subtask #8
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	60508 KB	Output is correct
2	Correct	33 ms	60504 KB	Output is correct
3	Correct	33 ms	60504 KB	Output is correct

Subtask #9
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	123 ms	70484 KB	Output is correct
2	Correct	127 ms	70804 KB	Output is correct
3	Correct	114 ms	70876 KB	Output is correct

Subtask #10
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	267 ms	90400 KB	Output is correct
2	Correct	107 ms	64820 KB	Output is correct
3	Correct	80 ms	85832 KB	Output is correct
4	Correct	433 ms	93776 KB	Output is correct

Subtask #11
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	379 ms	93268 KB	Output is correct
2	Correct	446 ms	94896 KB	Output is correct
3	Correct	228 ms	88148 KB	Output is correct

Subtask #12
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	320 ms	91220 KB	Output is correct
2	Correct	628 ms	97528 KB	Output is correct
3	Correct	607 ms	97104 KB	Output is correct
4	Correct	635 ms	97324 KB	Output is correct
5	Correct	573 ms	97364 KB	Output is correct
6	Correct	227 ms	87764 KB	Output is correct

Subtask #13
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	399 ms	116512 KB	Output is correct
2	Correct	218 ms	111444 KB	Output is correct

Subtask #14
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	511 ms	121680 KB	Output is correct
2	Correct	550 ms	125516 KB	Output is correct
3	Correct	392 ms	117436 KB	Output is correct

Subtask #15
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	653 ms	127024 KB	Output is correct
2	Correct	813 ms	135748 KB	Output is correct
3	Correct	839 ms	135548 KB	Output is correct
4	Correct	682 ms	133188 KB	Output is correct
5	Correct	530 ms	127628 KB	Output is correct

Submission #1027117

Compilation message