#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000;
struct segment_tree{
int N;
vector<long long> sum, left;
segment_tree(int N2){
N = 1;
while (N < N2){
N *= 2;
}
sum = vector<long long>(N * 2 - 1, INF);
left = vector<long long>(N * 2 - 1, INF);
for (int i = 0; i < N2; i++){
sum[N - 1 + i] = 0;
left[N - 1 + i] = 0;
}
for (int i = N - 2; i >= 0; i--){
sum[i] = sum[i * 2 + 1] + sum[i * 2 + 2];
left[i] = 0;
}
}
void add(int i, long long x){
i += N - 1;
sum[i] += x;
left[i] = sum[i];
while (i > 0){
i = (i - 1) / 2;
sum[i] = sum[i * 2 + 1] + sum[i * 2 + 2];
left[i] = min(left[i * 2 + 1], sum[i * 2 + 1] + min(left[i * 2 + 2], (long long) 0));
}
}
long long get(){
return left[0];
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int M, N;
cin >> M >> N;
int B;
cin >> B;
int P;
cin >> P;
vector<int> X1(P), Y1(P), X2(P), Y2(P), C(P);
for (int i = 0; i < P; i++){
cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i] >> C[i];
X1[i]--;
Y1[i]--;
}
int tv = 0, fv = min(M, N) + 1;
segment_tree ST(M);
while (fv - tv > 1){
int mid = (tv + fv) / 2;
vector<tuple<int, int, int>> T;
for (int i = 0; i < P; i++){
T.push_back(make_tuple(max(Y1[i] - mid + 1, 0), i, 0));
T.push_back(make_tuple(Y2[i], i, 1));
}
sort(T.begin(), T.end());
int cnt = T.size();
bool ok = false;
for (int i = 0; i < cnt; i++){
int j = get<1>(T[i]);
int t = get<2>(T[i]);
if (t == 0){
ST.add(max(X1[j] - mid + 1, 0), C[j]);
if (X2[j] < M - mid + 1){
ST.add(X2[j], -C[j]);
}
}
if (t == 1){
ST.add(max(X1[j] - mid + 1, 0), -C[j]);
if (X2[j] < M - mid + 1){
ST.add(X2[j], C[j]);
}
}
if (i < cnt - 1){
if (get<0>(T[i]) != get<0>(T[i + 1])){
if (ST.get() <= B){
ok = true;
}
}
}
}
if (ok){
tv = mid;
} else {
fv = mid;
}
}
cout << tv << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
852 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
4504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
38 ms |
33216 KB |
Output is correct |
2 |
Correct |
34 ms |
33236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
35 ms |
33192 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
39 ms |
1256 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
231 ms |
5544 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
524 ms |
34860 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
607 ms |
35088 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
778 ms |
35212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5095 ms |
47988 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5101 ms |
58452 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5105 ms |
62872 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |