oj.uz

Submission #884461

# Submission time Handle Problem Language Result Execution time Memory
884461 2023-12-07T12:00:40 Z Tob Pyramid Base (IOI08_pyramid_base) C++14
80 / 100
 5000 ms 112216 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 84568 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 84572 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 84804 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 84780 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 84800 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 84824 KB Output is correct
2 Correct 231 ms 84800 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 84812 KB Output is correct
2 Correct 232 ms 84824 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 85180 KB Output is correct
2 Correct 151 ms 85320 KB Output is correct
3 Correct 144 ms 85544 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 87452 KB Output is correct
2 Correct 440 ms 88160 KB Output is correct
3 Correct 375 ms 87964 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 826 ms 90164 KB Output is correct
2 Correct 199 ms 86160 KB Output is correct
3 Correct 219 ms 89756 KB Output is correct
4 Correct 1092 ms 94068 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1072 ms 93016 KB Output is correct
2 Correct 1119 ms 96012 KB Output is correct
3 Correct 765 ms 88204 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 986 ms 91280 KB Output is correct
2 Correct 1416 ms 98324 KB Output is correct
3 Correct 1522 ms 98324 KB Output is correct
4 Correct 1472 ms 98416 KB Output is correct
5 Correct 1460 ms 98068 KB Output is correct
6 Correct 744 ms 87392 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4467 ms 100336 KB Output is correct
2 Correct 3359 ms 96580 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5027 ms 105552 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5012 ms 112216 KB Time limit exceeded
2 Halted 0 ms 0 KB -