oj.uz

Submission #1027089

# Submission time Handle Problem Language Result Execution time Memory
1027089 2024-07-18T20:39:44 Z Tob Pyramid Base (IOI08_pyramid_base) C++14
80 / 100
 5000 ms 143320 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 59992 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 59992 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 59992 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 59996 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 66392 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 76372 KB Output is correct
2 Correct 89 ms 81492 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 82768 KB Output is correct
2 Correct 36 ms 78412 KB Output is correct

Subtask #8
7.0 / 7.0

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

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 69120 KB Output is correct
2 Correct 121 ms 69460 KB Output is correct
3 Correct 115 ms 69456 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 88656 KB Output is correct
2 Correct 116 ms 64848 KB Output is correct
3 Correct 87 ms 84048 KB Output is correct
4 Correct 439 ms 92120 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 91480 KB Output is correct
2 Correct 541 ms 93812 KB Output is correct
3 Correct 226 ms 86948 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 90192 KB Output is correct
2 Correct 619 ms 96408 KB Output is correct
3 Correct 614 ms 96084 KB Output is correct
4 Correct 578 ms 96336 KB Output is correct
5 Correct 604 ms 96340 KB Output is correct
6 Correct 242 ms 86888 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3810 ms 129716 KB Output is correct
2 Correct 1785 ms 103504 KB Output is correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5046 ms 136452 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 5019 ms 143320 KB Time limit exceeded
2 Halted 0 ms 0 KB -