Submission #1027117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027117		Tob	Pyramid Base (IOI08_pyramid_base)	C++14	100 / 100	839 ms	135748 KiB

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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10