Submission #1027089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027089		Tob	Pyramid Base (IOI08_pyramid_base)	C++14	80 / 100	5046 ms	143320 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;

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];

inline pii Merge(pii x, pii y) {return {x.F+y.F, min(x.S, x.F+y.S)};}
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;}

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];
	}
	
	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";

	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: 0 / 10
• Subtask 15: 0 / 10