#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ldb;
const int INF = 1e9 + 228;
struct obstacle {
int x1, y1, x2, y2, cost;
};
int n, m;
int p;
int q;
vector<obstacle> obstacles;
const int MAXN = 1e6 + 228;
int tree[4 * MAXN];
int mod[4 * MAXN];
void push(int v, int l, int r) {
tree[v] += mod[v];
if (l + 1 != r) {
mod[2 * v + 1] += mod[v];
mod[2 * v + 2] += mod[v];
}
mod[v] = 0;
}
void add(int v, int l, int r, int ql, int qr, int val) {
push(v, l, r);
if (l >= qr || ql >= r) {
return;
}
if (ql <= l && r <= qr) {
mod[v] += val;
push(v, l, r);
return;
}
int m = (l + r) / 2;
add(2 * v + 1, l, m, ql, qr, val);
add(2 * v + 2, m, r, ql, qr, val);
tree[v] = min(tree[2 * v + 1], tree[2 * v + 2]);
}
void add(int l, int r, int val) {
add(0, 0, m, l, r, val);
}
int get(int v, int l, int r, int ql, int qr) {
push(v, l, r);
if (l >= qr || ql >= r) {
return INF;
}
if (ql <= l && r <= qr) {
return tree[v];
}
int m = (l + r) / 2;
return min(get(2 * v + 1, l, m, ql, qr), get(2 * v + 2, m, r, ql, qr));
}
int get_mn(int l, int r) {
return get(0, 0, m, l, r);
}
bool canBuild(int r) {
vector<array<int, 4>> qq; // {time, l, r, val}
for (int i = 0; i < q; i++) {
qq.push_back({max(0, obstacles[i].x1 - r + 1), max(0, obstacles[i].y1 - r + 1), obstacles[i].y2, obstacles[i].cost});
qq.push_back({obstacles[i].x2, max(0, obstacles[i].y1 - r + 1), obstacles[i].y2, -obstacles[i].cost});
}
qq.push_back({0, 0, m, 0});
qq.push_back({n, 0, m, 0});
sort(qq.begin(), qq.end());
int last_time = 0;
bool ans = 0;
for (auto el : qq) {
if (el[0] != last_time && last_time + r <= n) {
int el = get_mn(0, m - r + 1);
if (el <= p) {
ans = 1;
}
}
last_time = el[0];
add(el[1], el[2], el[3]);
}
return ans;
}
void solve() {
cin >> n >> m >> p >> q;
obstacles.resize(q);
for (int i = 0; i <q; i++) {
cin >> obstacles[i].x1;
cin >> obstacles[i].y1;
cin >> obstacles[i].x2;
cin >> obstacles[i].y2;
cin >> obstacles[i].cost;
obstacles[i].x1--;
obstacles[i].y1--;
}
int L = 0;
int R = min(n, m) + 1;
while (R - L > 1) {
int M = (L + R) / 2;
if (canBuild(M)) {
L = M;
} else {
R = M;
}
}
cout << L << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
2472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
10712 KB |
Output is correct |
2 |
Correct |
40 ms |
16572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
49 ms |
16472 KB |
Output is correct |
2 |
Correct |
31 ms |
11224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
1200 KB |
Output is correct |
2 |
Correct |
94 ms |
1368 KB |
Output is correct |
3 |
Correct |
76 ms |
1232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
399 ms |
4040 KB |
Output is correct |
2 |
Correct |
411 ms |
4260 KB |
Output is correct |
3 |
Correct |
391 ms |
4052 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
700 ms |
19380 KB |
Output is correct |
2 |
Correct |
86 ms |
2872 KB |
Output is correct |
3 |
Correct |
303 ms |
19224 KB |
Output is correct |
4 |
Correct |
947 ms |
19508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
986 ms |
19968 KB |
Output is correct |
2 |
Correct |
1014 ms |
19888 KB |
Output is correct |
3 |
Correct |
743 ms |
19972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
948 ms |
20168 KB |
Output is correct |
2 |
Correct |
1378 ms |
20244 KB |
Output is correct |
3 |
Correct |
1402 ms |
20164 KB |
Output is correct |
4 |
Correct |
1348 ms |
20348 KB |
Output is correct |
5 |
Correct |
1293 ms |
20232 KB |
Output is correct |
6 |
Correct |
689 ms |
20408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5052 ms |
40956 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5066 ms |
57136 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
5054 ms |
65100 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |