#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using pd = pair<db, db>;
using vi = vector<int>;
using vb = vector<bool>;
using vl = vector<ll>;
using vd = vector<db>;
using vs = vector<str>;
using vpi = vector<pi>;
using vpl = vector<pl>;
using vpd = vector<pd>;
#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define bg(x) begin(x)
#define all(x) bg(x), end(x)
#define sor(x) sort(all(x))
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pb push_back
#define pf push_front
#define lb lower_bound
#define ub upper_bound
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define R0F(i, a) ROF(i, 0, a)
#define EACH(a, x) for (auto& a : x)
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T> void remDup(vector<T>& v) { sor(v); v.erase(unique(all(v)), v.end()); }
const int MOD = 1e9 + 7;
const int MX = 1e6 + 10;
const ll INF = 1e18;
int M, N, B, P;
struct Subtask2 {
vector<array<int, 3>> ST[MX], EN[MX]; int tree[4 * MX], lazy[4 * MX];
void pushdown(int x, int l, int r) {
if (lazy[x] == 0) return ; tree[x] += lazy[x];
if (l < r) { F0R(i, 2) lazy[2 * x + i] += lazy[x]; } lazy[x] = 0;
}
void update(int x, int l, int r, int tl, int tr, int val) { int mid = (l + r) / 2;
pushdown(x, l, r); if (l > tr || r < tl) return ; if (tl <= l && r <= tr) { lazy[x] = val; pushdown(x, l, r); return ; }
update(2 * x, l, mid, tl, tr, val); update(2 * x + 1, mid + 1, r, tl, tr, val); tree[x] = min(tree[2 * x], tree[2 * x + 1]);
}
void init() {
F0R(i, P) {
int X1, Y1, X2, Y2, C; cin >> X1 >> Y1 >> X2 >> Y2 >> C;
ST[X1].pb({Y1, Y2, C}); EN[X2 + 1].pb({Y1, Y2, -C});
}
}
int solve() {
int low = 0; int high = min(M, N); int res = 0;
while (low <= high) { int mid = (low + high) / 2;
F0R(i, 4 * N) tree[i] = 0, lazy[i] = 0; update(1, 1, N, N - mid + 2, N, MOD);
FOR(i, 1, mid) EACH(C, ST[i]) update(1, 1, N, max(1, C[0] - mid + 1), C[1], C[2]);
bool valid = false; FOR(i, 1, M - mid + 2) {
EACH(C, ST[i + mid - 1]) update(1, 1, N, max(1, C[0] - mid + 1), C[1], C[2]);
EACH(C, EN[i]) update(1, 1, N, max(1, C[0] - mid + 1), C[1], C[2]);
valid = tree[1] <= B; if (valid) break;
}
if (valid) low = mid + 1, res = mid; else high = mid - 1;
}
return res;
}
};
struct Subtask3 {
vector<array<int, 2>> ST[MX], EN[MX];
struct Node { int L, R, ans, sum; } tree[4 * MX]; int lazy[4 * MX];
void comb(int x, int l, int r) { int mid = (l + r) / 2;
tree[x].sum = tree[2 * x].sum + tree[2 * x + 1].sum;
tree[x].ans = max({tree[2 * x].ans, tree[2 * x + 1].ans, tree[2 * x].R + tree[2 * x + 1].L});
tree[x].L = tree[2 * x].L == mid - l + 1 ? (tree[2 * x].L + tree[2 * x + 1].L) : tree[2 * x].L;
tree[x].R = tree[2 * x + 1].R == r - mid ? (tree[2 * x + 1].R + tree[2 * x].R) : tree[2 * x + 1].R;
}
void pushdown(int x, int l, int r) { int mid = (l + r) / 2;
if (lazy[x] == 0) return ; tree[x].sum += lazy[x]; if (tree[x].sum > 0) tree[x].L = tree[x].R = tree[x].ans = 0;
if (l < r) F0R(i, 2) lazy[2 * x + i] += lazy[x]; lazy[x] = 0;
}
void build(int x, int l, int r) { int mid = (l + r) / 2;
if (l == r) { tree[x].L = tree[x].R = tree[x].ans = 1; return ; }
build(2 * x, l, mid); build(2 * x + 1, mid + 1, r); comb(x, l, r);
}
void update(int x, int l, int r, int tl, int tr, int val) { int mid = (l + r) / 2;
pushdown(x, l, r); if (l > tr || r < tl) return ; if (tl <= l && r <= tr) { lazy[x] = val; pushdown(x, l, r); return ; }
update(2 * x, l, mid, tl, tr, val); update(2 * x + 1, mid + 1, r, tl, tr, val); comb(x, l, r);
}
void init() {
F0R(i, P) {
int X1, Y1, X2, Y2, C; cin >> X1 >> Y1 >> X2 >> Y2 >> C;
ST[X1].pb({Y1, Y2}); EN[X2 + 1].pb({Y1, Y2});
}
}
int solve() {
int ans = 0; int R = 1; build(1, 1, N);
FOR(L, 1, M + 1) {
EACH(C, EN[L]) update(1, 1, N, C[0], C[1], -1);
while (R <= M && tree[1].ans >= R - L + 1) {
EACH(C, ST[R]) update(1, 1, N, C[0], C[1], 1); R++;
}
ckmax(ans, R - L + 1);
}
return ans;
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> M >> N >> B >> P; if (B) { Subtask2 S; S.init(); cout << S.solve(); } else { Subtask3 S; S.init(); cout << S.solve(); }
}
Compilation message
pyramid_base.cpp: In member function 'void Subtask2::pushdown(int, int, int)':
pyramid_base.cpp:65:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
65 | if (lazy[x] == 0) return ; tree[x] += lazy[x];
| ^~
pyramid_base.cpp:65:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
65 | if (lazy[x] == 0) return ; tree[x] += lazy[x];
| ^~~~
pyramid_base.cpp: In member function 'int Subtask2::solve()':
pyramid_base.cpp:41:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
41 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
| ^~~
pyramid_base.cpp:42:19: note: in expansion of macro 'FOR'
42 | #define F0R(i, a) FOR(i, 0, a)
| ^~~
pyramid_base.cpp:86:13: note: in expansion of macro 'F0R'
86 | F0R(i, 4 * N) tree[i] = 0, lazy[i] = 0; update(1, 1, N, N - mid + 2, N, MOD);
| ^~~
pyramid_base.cpp:86:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
86 | F0R(i, 4 * N) tree[i] = 0, lazy[i] = 0; update(1, 1, N, N - mid + 2, N, MOD);
| ^~~~~~
pyramid_base.cpp: In member function 'void Subtask3::pushdown(int, int, int)':
pyramid_base.cpp:117:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
117 | if (lazy[x] == 0) return ; tree[x].sum += lazy[x]; if (tree[x].sum > 0) tree[x].L = tree[x].R = tree[x].ans = 0;
| ^~
pyramid_base.cpp:117:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
117 | if (lazy[x] == 0) return ; tree[x].sum += lazy[x]; if (tree[x].sum > 0) tree[x].L = tree[x].R = tree[x].ans = 0;
| ^~~~
pyramid_base.cpp:116:46: warning: unused variable 'mid' [-Wunused-variable]
116 | void pushdown(int x, int l, int r) { int mid = (l + r) / 2;
| ^~~
pyramid_base.cpp: In member function 'int Subtask3::solve()':
pyramid_base.cpp:45:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
45 | #define EACH(a, x) for (auto& a : x)
| ^~~
pyramid_base.cpp:146:17: note: in expansion of macro 'EACH'
146 | EACH(C, ST[R]) update(1, 1, N, C[0], C[1], 1); R++;
| ^~~~
pyramid_base.cpp:146:64: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
146 | EACH(C, ST[R]) update(1, 1, N, C[0], C[1], 1); R++;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
125516 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
125520 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
125464 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
125544 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
125556 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
125612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
86 ms |
125636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
84 ms |
125832 KB |
Output is correct |
| 2 |
Correct |
125 ms |
125900 KB |
Output is correct |
| 3 |
Correct |
108 ms |
125888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
275 ms |
126792 KB |
Output is correct |
| 2 |
Correct |
437 ms |
126788 KB |
Output is correct |
| 3 |
Correct |
362 ms |
126704 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
628 ms |
127320 KB |
Output is correct |
| 2 |
Correct |
93 ms |
127172 KB |
Output is correct |
| 3 |
Correct |
271 ms |
126736 KB |
Output is correct |
| 4 |
Correct |
720 ms |
127408 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
910 ms |
128016 KB |
Output is correct |
| 2 |
Correct |
1313 ms |
127636 KB |
Output is correct |
| 3 |
Correct |
658 ms |
127952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
989 ms |
128256 KB |
Output is correct |
| 2 |
Correct |
1652 ms |
128020 KB |
Output is correct |
| 3 |
Correct |
1647 ms |
128128 KB |
Output is correct |
| 4 |
Correct |
1698 ms |
128176 KB |
Output is correct |
| 5 |
Correct |
1670 ms |
128196 KB |
Output is correct |
| 6 |
Correct |
742 ms |
128452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
653 ms |
142708 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
872 ms |
150460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1101 ms |
157896 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
