This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int Z = 4e5+1, LIM = 1e6+1;
const ll INF = 1e18;
int sL, sR;
ll sV;
struct ST0 {
int l, r;
ll v {}, add {};
ST0 *L, *R;
ST0(int lv, int rv) : l(lv), r(rv) {
if(r - l > 1) {
int m = (l + r) / 2;
L = new ST0(l, m);
R = new ST0(m, r);
}
}
void rangeAdd(int lv, int rv, ll val) {
sL = lv, sR = rv + 1, sV = val;
rangeAdd();
}
void rangeAdd() {
if(sR <= l || r <= sL) return;
if(sL <= l && r <= sR) {
add += sV;
v += sV;
return;
}
L->rangeAdd();
R->rangeAdd();
v = min(L->v, R->v) + add;
}
void clear() {
if(r - l > 1) L->clear(), R->clear();
add = v = 0;
}
};
struct ST1 {
int l, r, add {};
array<int, 3> v;
ST1 *L, *R;
ST1(int lv, int rv) : l(lv), r(rv) {
v = {r - l, r - l, r - l};
if(r - l > 1) {
int m = (l + r) / 2;
L = new ST1(l, m);
R = new ST1(m, r);
}
}
void pull() {
if(add || r - l < 2) v = {!add, !add, !add};
else {
int m = (l + r) / 2;
bool lf = L->v[0] == m - l, rf = R->v[0] == r - m;
v = {max(L->v[2] + R->v[1], max(L->v[0], R->v[0])), L->v[1] + (lf ? R->v[1] : 0), R->v[2] + (rf ? L->v[2] : 0)};
}
}
void rangeAdd(int lv, int rv, int val) {
sL = lv, sR = rv + 1, sV = val;
rangeAdd();
}
void rangeAdd() {
if(sR <= l || r <= sL) return;
if(sL <= l && r <= sR) return add += sV, pull();
L->rangeAdd();
R->rangeAdd();
pull();
}
};
int M, N, B, P;
vector<array<ll, 3>> a[2][LIM];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> B >> P;
for(int i = 0; i < P; ++i) {
array<ll, 5> u;
for(ll &j : u) cin >> j;
a[0][u[0]].push_back({u[1], u[3], u[4]});
a[1][u[2]].push_back({u[1], u[3], u[4]});
}
int x = 0;
if(B) {
ST0* st = new ST0(1, M + 1);
for(int y = 1<<20; y /= 2; ) if(x + y <= min(M, N)) {
x ^= y;
bool ok = 0;
st->rangeAdd(M - x + 2, M, INF);
for(int i = 1; i <= N && !ok; ++i) {
for(const auto &[l, r, v] : a[0][i])
st->rangeAdd(l - x + 1, r, v);
if(i < x) continue;
for(const auto &[l, r, v] : a[1][i-x])
st->rangeAdd(l - x + 1, r, -v);
ok = st->v <= B;
}
st->clear();
if(!ok) x ^= y;
}
} else {
ST1* st = new ST1(1, M + 1);
for(int i = 1, j = 1; i <= N; ++i) {
for(const auto &[l, r, v] : a[1][i-1])
st->rangeAdd(l, r, -1);
for(; j <= N && j - i < st->v[0]; ++j) {
x = max(x, j - i);
for(const auto &[l, r, v] : a[0][j])
st->rangeAdd(l, r, 1);
}
x = max(x, min(j - i, st->v[0]));
}
}
cout << x;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |