#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;
#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"
template<class X, class Y>
bool minz(X &x, const Y &y) {
if (x > y) {
x = y;
return true;
} return false;
}
template<class X, class Y>
bool maxz(X &x, const Y &y) {
if (x < y) {
x = y;
return true;
} return false;
}
const int N = 2e6 + 5;
const ll oo = (ll) 1e16;
const ll mod = 1e9 + 7; // 998244353;
ll n, m, b, p;
namespace sub2{
int tree[N * 4], lazy[N * 4], sz;
vector <piii> add[2 * N], rem[2 * N];
vector <int> co;
void down (int i){
if (!lazy[i]) return;
forr (j, i << 1, (i << 1) | 1){
//cout << i << " " << j << "\n";
tree[j] += lazy[i];
lazy[j] += lazy[i];
}
lazy[i] = 0;
}
void update(int i, int l, int r, int u, int v, int val){
if (l > v || r < u) return;
if (l >= u && r <= v){
//cout << i << " " << l << " " << r << " " << val << "\n";
tree[i] += val;
lazy[i] += val;
return;
}
down(i);
int mid = (l + r) >> 1;
update(i << 1, l, mid, u, v, val);
update(i << 1 | 1, mid + 1, r, u, v, val);
tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
//cout << i << " " << tree[i] << "\n";
}
int get (int i, int l, int r, int u, int v){
if (u > r || v < l) return 2 * mod;
if (l >= u && r <= v) return tree[i];
down(i);
int mid = (l + r) >> 1;
return min(get(i << 1, l, mid, u, v), get(i << 1 | 1, mid + 1, r, u, v));
}
int calc(int len){
if (!len) return 0;
memset (tree, 0, sizeof tree);
memset (lazy, 0, sizeof lazy);
int z = upper_bound(all(co), len) - co.begin();
int res = 2 * mod;
forr (i, 1, n){
int flag = (i == len);
// cout << i << ":\n";
for (piii t : add[i]){
flag = 1;
int u = upper_bound(all(co), t.nd.nd + len - 1) - co.begin();
int v = lower_bound(all(co), t.nd.st) - co.begin();
//cout << "add " << t.nd.st << " " << t.nd.nd << " " << v << " " << u << " " << t.st << "\n";
update(1, 1, m, t.nd.st, min(m, (ll)t.nd.nd + len - 1), t.st);
}
if (i >= len){
for (piii t : rem[i - len]){
flag = 1;
int u = upper_bound(all(co), t.nd.nd + len - 1) - co.begin();
int v = lower_bound(all(co), t.nd.st) - co.begin() + 1;
//cout << "rem " << t.nd.st << " " << t.nd.nd << " " << v << " " << u << "\n";
update(1, 1, m, t.nd.st, min(m, (ll)t.nd.nd + len - 1), -t.st);
}
}
if (i >= len && flag){
res = min (res, get(1, 1, m, len, m));
//cout << tree[1] << "\n";
}
}
return res;
}
void solve(){
forr (i, 1, p){
int x, y, u, v, w;
cin >> x >> y >> u >> v >> w;
add[x].pb({w, {y, v}});
rem[u].pb({w, {y, v}});
co.pb(y);
co.pb(v);
}
co.pb(m);
sort(all(co));
co.erase(unique(all(co)), co.end());
sz = co.size();
//cout << sz << "\n";
// for (int u : co){
// cout << u << " ";
// }
// cout << "\n";
// cout << calc(33541) << "\n";
int l = 0, r = min(n, m);
while (l < r){
int mid = (l + r + 1) >> 1;
if (calc(mid) <= b)
l = mid;
else r = mid - 1;
}
cout << l << "\n";
}
}
namespace sub3{
struct node{
int val, mx, pre, suf, len;
node(){}
node(ll x) : val(x), mx(1), pre(1), suf(1), len(1){}
};
node comb (node u, node v){
node res;
if (u.val == v.val){
res.val = u.val;
res.pre = u.pre;
res.suf = v.suf;
if (u.suf == u.len) res.pre += v.pre;
if (v.pre == v.len) res.suf += u.suf;
res.mx = max (u.suf + v.pre, max(u.mx, v.mx));
res.len = u.len + v.len;
} else
if (u.val < v.val){
res.val = u.val;
res.pre = u.pre;
res.suf = 0;
res.mx = u.mx;
res.len = u.len + v.len;
} else {
res.val = v.val;
res.suf = v.suf;
res.pre = 0;
res.mx = v.mx;
res.len = u.len + v.len;
}
return res;
}
node tree[N << 2];
int lazy[N << 2];
void down (int i){
if (lazy[i] == 0)
return;
lazy[(i << 1)] += lazy[i];
lazy[(i << 1) | 1] += lazy[i];
tree[(i << 1)].val += lazy[i];
tree[(i << 1) | 1].val += lazy[i];
lazy[i] = 0;
}
void build (int i, int l, int r){
if (l == r){
tree[i] = node(0);
return;
}
int mid = (l + r) >> 1;
build(i << 1, l, mid);
build(i << 1 | 1, mid + 1, r);
tree[i] = comb(tree[i << 1], tree[i << 1 | 1]);
}
void update (int i, int l, int r, int u, int v, ll val){
if (l > v || r < u)
return;
if (l >= u && r <= v){
tree[i].val += val;
lazy[i] += val;
return;
}
down(i);
int mid = (l + r) >> 1;
update ((i << 1), l, mid, u, v, val);
update ((i << 1) | 1, mid + 1, r ,u, v, val);
tree[i] = comb (tree[(i << 1)], tree[(i << 1) | 1]);
}
vector <pii> add[2 * N], rem[2 * N];
int f[N];
void solve(){
forr (i, 1, p){
int x, y, u, v, w;
cin >> x >> y >> u >> v >> w;
add[x].pb({y, v});
rem[u].pb({y, v});
}
f[0] = 0;
build(1, 1, m);
int res = 0;
forr (i, 1, n){
for (pii t : rem[i - 1]){
update(1, 1, m, t.st, t.nd, -1);
}
f[i] = f[i - 1];
while (f[i] <= n && tree[1].val == 0 && tree[1].mx >= f[i] - i){
res = max (res, f[i] - i);
f[i]++;
for (pii t : add[f[i]]){
update(1, 1, m, t.st, t.nd, 1);
}
}
}
cout << res << "\n";
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef hqm
freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
#endif
cin >> n >> m >> b >> p;
if (b > 0) sub2::solve();
else sub3::solve();
return 0;
}
/*
*/
Compilation message
pyramid_base.cpp: In function 'int sub2::calc(int)':
pyramid_base.cpp:93:21: warning: unused variable 'u' [-Wunused-variable]
93 | int u = upper_bound(all(co), t.nd.nd + len - 1) - co.begin();
| ^
pyramid_base.cpp:94:21: warning: unused variable 'v' [-Wunused-variable]
94 | int v = lower_bound(all(co), t.nd.st) - co.begin();
| ^
pyramid_base.cpp:101:25: warning: unused variable 'u' [-Wunused-variable]
101 | int u = upper_bound(all(co), t.nd.nd + len - 1) - co.begin();
| ^
pyramid_base.cpp:102:25: warning: unused variable 'v' [-Wunused-variable]
102 | int v = lower_bound(all(co), t.nd.st) - co.begin() + 1;
| ^
pyramid_base.cpp:86:13: warning: unused variable 'z' [-Wunused-variable]
86 | int z = upper_bound(all(co), len) - co.begin();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
85 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
86 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
85 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
89 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
100 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
99 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
96 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
87 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
86 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
99 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
96 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
88 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
90 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
88 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
87 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
