#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Rect {
int x1;
int y1;
int x2;
int y2;
int cost;
};
const int N = (int) 4e5 + 7;
const int L = (int) 1e6 + 7;
const int INF = (int) 1e9 + 7;
int dimx;
int dimy;
int budget;
int n;
int initN;
Rect rects[N], initRects[N];
struct Node {
ll mn;
int len;
int sol;
int pref;
int suf;
};
Node tree[4 * L];
ll lazy[4 * L];
Node operator + (Node a, Node b) {
int mn = min(a.mn, b.mn);
int len = a.len + b.len;
int sol;
int pref;
int suf;
if (a.mn == b.mn) {
sol = max(a.suf + b.pref, max(a.sol, b.sol));
pref = a.pref + b.pref * (a.pref == a.len);
suf = b.suf + a.suf * (b.suf == b.len);
} else {
if (a.mn < b.mn) {
sol = a.sol;
pref = a.pref;
suf = 0;
} else {
sol = b.sol;
pref = 0;
suf = b.suf;
}
}
return {mn, len, sol, pref, suf};
}
void build(int v, int tl, int tr) {
lazy[v] = 0;
if (tl == tr) {
tree[v].mn = 0;
tree[v].len = 1;
tree[v].sol = 1;
tree[v].pref = 1;
tree[v].suf = 1;
return;
}
int tm = (tl + tr) / 2;
build(2 * v, tl, tm);
build(2 * v + 1, tm + 1, tr);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
void push(int v, int tl, int tr) {
if (lazy[v]) {
tree[v].mn += lazy[v];
if (tl < tr) {
lazy[2 * v] += lazy[v];
lazy[2 * v + 1] += lazy[v];
}
lazy[v] = 0;
}
}
void add(int v, int tl, int tr, int l, int r, int x) {
push(v, tl, tr);
if (tr < l || r < tl) {
return;
}
if (l <= tl && tr <= r) {
lazy[v] += x;
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
add(2 * v, tl, tm, l, r, x);
add(2 * v + 1, tm + 1, tr, l, r, x);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
void build() {
build(1, 1, dimy);
}
void add(int l, int r, int x) {
add(1, 1, dimy, l, r, x);
}
int get() {
/// cout << tree[1].mn << " " << tree[1].len << " ---> " << tree[1].sol << "\n";
if (tree[1].mn == 0) {
return tree[1].sol;
} else {
return 0;
}
}
vector<int> out[L];
vector<int> in[L];
bool isok(int len) {
for (int x = 1; x + len - 1 <= dimx; x++) {
for (int y = 1; y + len - 1 <= dimy; y++) {
ll thecost = 0;
for (int i = 1; i <= n; i++) {
bool outside = 0;
outside |= (x + len - 1 < rects[i].x1);
outside |= (y + len - 1 < rects[i].y1);
outside |= (rects[i].x2 < x);
outside |= (rects[i].y2 < x);
if (!outside) {
thecost += rects[i].cost;
}
}
if (thecost <= budget) {
return 1;
}
}
}
return 0;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
///freopen ("input", "r", stdin);
cin >> dimx >> dimy >> budget >> n;
initN = n;
for (int i = 1; i <= n; i++) {
cin >> rects[i].x1 >> rects[i].y1 >> rects[i].x2 >> rects[i].y2 >> rects[i].cost;
in[rects[i].x1].push_back(i);
out[rects[i].x2].push_back(i);
initRects[i] = rects[i];
}
build();
if (budget) {
///assert(0);
///cout << "I will think later about how to solve this subtask\n";
int low = 1, high = min(dimx, dimy), solution = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (isok(mid)) {
solution = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << solution << "\n";
return 0;
}
int missed = 0;
int x2 = 0, sol = 0;
for (int x1 = 1; x1 <= dimx; x1++) {
if (x2 >= x1 - 1) {
for (auto &i : out[x1 - 1]) {
add(rects[i].y1, rects[i].y2, -1);
}
}
x2 = max(x2, x1 - 1);
while (x2 <= dimx && x2 - x1 + 1 <= get()) {
x2++;
for (auto &i : in[x2]) {
add(rects[i].y1, rects[i].y2, +1);
}
if (x2 - x1 + 1 > get()) {
break;
}
}
sol = max(sol, x2 - x1);
}
cout << sol << "\n";
return 0;
}
Compilation message
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:179:7: warning: unused variable 'missed' [-Wunused-variable]
179 | int missed = 0;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
47300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
47308 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
47432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
48324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
31 ms |
55616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
80 ms |
113080 KB |
Output is correct |
| 2 |
Correct |
82 ms |
113036 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
113092 KB |
Output is correct |
| 2 |
Correct |
74 ms |
112960 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
628 ms |
48848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5054 ms |
57012 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5020 ms |
115100 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5037 ms |
115616 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5111 ms |
116052 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
855 ms |
132352 KB |
Output is correct |
| 2 |
Correct |
394 ms |
69720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1072 ms |
141144 KB |
Output is correct |
| 2 |
Correct |
1058 ms |
137176 KB |
Output is correct |
| 3 |
Correct |
618 ms |
129088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1300 ms |
149692 KB |
Output is correct |
| 2 |
Correct |
1479 ms |
147028 KB |
Output is correct |
| 3 |
Correct |
1452 ms |
147028 KB |
Output is correct |
| 4 |
Correct |
1348 ms |
144548 KB |
Output is correct |
| 5 |
Correct |
913 ms |
138900 KB |
Output is correct |
