#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
int st[2097157];
int lz[2097157];
int len = 1;
void init(int n){
len = 1;
while(len < n) len *= 2;
for (int i = len; i < len + n; i++) {
st[i] = 0;
lz[i] = 0;
}
for (int i = len + n; i < 2 * len; i++){
st[i] = INT_MAX;
lz[i] = 0;
}
for (int i = len - 1; i > 0; i--) {
st[i] = min(st[i * 2], st[i * 2 + 1]);
lz[i] = 0;
}
}
void prop(int i){
st[i * 2] += lz[i];
st[i * 2 + 1] += lz[i];
lz[i * 2] += lz[i];
lz[i * 2 + 1] += lz[i];
lz[i] = 0;
}
void add(int f, int t, int v, int i = 1, int s = 0, int e = len){
if(f >= e || s >= t) return;
if(f <= s && e <= t){
st[i] += v;
lz[i] += v;
return;
}
prop(i);
add(f, t, v, i * 2, s, (s + e) / 2);
add(f, t, v, i * 2 + 1, (s + e) / 2, e);
st[i] = min(st[i * 2], st[i * 2 + 1]);
}
vector<tuple<int, int, int>> ev[1000005]; //[y][i] -> t(0s, 1e), x, xx
array<int, 5> nv[400005];
vector<array<int, 5>> v;
bool can(int d, int w, int h){
w -= d;
h -= d;
for (int i = 0; i < v.size(); i++) {
nv[i] = v[i];
nv[i][0] -= d;
nv[i][1] -= d;
nv[i][0] = max(0, nv[i][0]);
nv[i][1] = max(0, nv[i][1]);
nv[i][2] = min(w - 1, nv[i][2]);
nv[i][3] = min(h - 1, nv[i][3]);
}
init(w);
for (int i = 0; i < 1000005; i++) {
ev[i] = {};
}
for (int j = 0; j < v.size(); j++) {
auto& i = nv[j];
ev[i[1]].push_back({0, i[0], i[2]});
ev[i[3] + 1].push_back({1, i[0], i[2]});
}
int y = 0;
for (auto& es : ev) {
for (auto& e : es) {
auto& [t, x, xx] = e;
if(t == 0){
add(x, xx + 1, 1);
}
else{
add(x, xx + 1, -1);
}
}
if(y >= h) break;
if(st[1] == 0) return true;
y++;
}
return false;
}
int main()
{
int w, h; cin >> w >> h;
int b; cin >> b;
if(b != 0) return 1;
int n; cin >> n;
v.resize(n);
for (auto &i : v){
cin >> i[0] >> i[1] >> i[2] >> i[3] >> i[4];
for (int j = 0; j < 4; j++)
i[j]--;
}
int l = -1, r = min(w, h), mid;
while(l < r){
mid = (l + r + 1) / 2;
if(can(mid, w, h)) l = mid;
else r = mid - 1;
}
cout << l + 1 << endl;
}
Compilation message
pyramid_base.cpp: In function 'bool can(int, int, int)':
pyramid_base.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 5> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
pyramid_base.cpp:72:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 5> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int j = 0; j < v.size(); j++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
29020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
29016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
29016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
29272 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
29660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
37676 KB |
Output is correct |
| 2 |
Correct |
148 ms |
42380 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
144 ms |
42448 KB |
Output is correct |
| 2 |
Correct |
82 ms |
37716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
26968 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
26972 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
26968 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
26972 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
27092 KB |
Execution failed because the return code was nonzero |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4119 ms |
86912 KB |
Output is correct |
| 2 |
Correct |
1518 ms |
117524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5032 ms |
98416 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5010 ms |
104484 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
