Submission #884461

#	Time	Username	Problem	Language	Result	Execution time	Memory
884461		Tob	Pyramid Base (IOI08_pyramid_base)	C++14	80 / 100	5027 ms	112216 KiB

pyramid_base

#include <bits/stdc++.h>

#define ll long long
#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 pair <int, int> pii;
typedef pair <pii, int> piii;

const int ofs = (1 << 20), P = 4e5 + 7, inf = 2e9 + 1;

int n, m, p, B;
int co[P][4], c[P];
ll t[2*ofs][2];
vector <piii> v[ofs][2];

void Merge(int x) {t[x][0] = min(t[2*x][0], t[2*x+1][0]);}
void Spo(ll& x, ll y) {
	if (!B) x = max(x, y);
	else x += y;
}

void Prop(int x) {
	if (!t[x][1]) return;
	if (B) t[x][0] += t[x][1];
	else Spo(t[x][0], t[x][1]);
	if (x < ofs) {
		Spo(t[2*x][1], t[x][1]);
		Spo(t[2*x+1][1], t[x][1]);
	}
	t[x][1] = 0;
}

void Update(int x, int a, int b, int val, int lo = 0, int hi = ofs-1) {
	Prop(x);
	if (hi < a || b < lo) return;
	if (a <= lo && hi <= b) {
		t[x][1] = 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);
	Merge(x);
}

int main () {
	FIO;
	cin >> n >> m >> B >> p;
	
	for (int i = 0; i < p; i++) {
		for (int j = 0; j < 4; j++) cin >> co[i][j];
		cin >> c[i];
		if (!B) c[i] = 1;
	}
	
	int lo = 0, hi = min(n, m);
	while (lo < hi) {
		int mid = (lo + hi + 1) / 2;
//		cout << mid << " --------\n";
		for (int i = ofs; i < 2*ofs; i++) {
			t[i][0] = inf;
			t[i][1] = 0;
		}
		for (int i = 1; i <= n; i++) t[i+ofs][0] = 0;
		for (int i = ofs-1; i; i--) {
			Merge(i);
			t[i][1] = 0;
			v[i][0].clear();
			v[i][1].clear();
		}
		if (B) Update(1, 1, n, inf);
		else if (!B && 1 < mid) {
			Update(1, 1, mid-1, inf);
		}
		if (!B) Update(1, mid, n, mid-1);
		for (int i = 0; i < p; i++) {
			if (B) {
				v[co[i][1]][0].pb({{co[i][0], min(co[i][2]+mid-1, n)}, c[i]});
				v[min(co[i][3]+mid, m+1)][1].pb({{co[i][0], min(co[i][2]+mid-1, n)}, c[i]});
			}
			else {
				v[co[i][1]][0].pb({{co[i][0], min(co[i][2]+mid-1, n)}, min(co[i][3]+mid, m+1)});
			}
		}
		if (B) v[mid][1].pb({{mid, n}, inf});
		int ok = 0;
		for (int i = 1; i <= m; i++) {
//			cout << i << "->\n";
			for (piii& it : v[i][0]) Update(1, it.F.F, it.F.S, it.S);
			for (piii& it : v[i][1]) Update(1, it.F.F, it.F.S, -it.S);
			if (B) ok |= (t[1][0] <= B);
			else ok |= (t[1][0] <= i);
		}
		if (ok) 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