#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#include <bits/stdc++.h>
using namespace std;
void just_do_it();
int main() {
#ifdef KAMIRULEZ
freopen("kamirulez.inp", "r", stdin);
freopen("kamirulez.out", "w", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
just_do_it();
return 0;
}
const int maxN = 1e6 + 20;
const int maxK = 4e5 + 20;
int tree[maxN << 2];
int lazy[maxN << 2];
int Lx[maxK];
int Ly[maxK];
int Rx[maxK];
int Ry[maxK];
int ly[maxK];
int ry[maxK];
int cnt_x[maxN];
int cnt_y[maxN];
int cost[maxK];
int order[maxK];
int queries[maxK << 2];
pair<int, int> events_x[maxK << 1];
pair<int, int> events_y[maxK << 1];
int N, M, B, K;
void reset(int id, int lt, int rt) {
tree[id] = 0;
lazy[id] = 0;
if (lt == rt) {
return;
}
int mt = (lt + rt) >> 1;
reset(id << 1, lt, mt);
reset(id << 1 | 1, mt + 1, rt);
}
void update(int id, int lt, int rt, int ql, int qr, int add) {
if (lt == ql && rt == qr) {
tree[id] += add;
lazy[id] += add;
return;
}
tree[id << 1] += lazy[id];
lazy[id << 1] += lazy[id];
tree[id << 1 | 1] += lazy[id];
lazy[id << 1 | 1] += lazy[id];
lazy[id] = 0;
int mt = (lt + rt) >> 1;
if (qr <= mt) {
update(id << 1, lt, mt, ql, qr, add);
}
else if (ql >= mt + 1) {
update(id << 1 | 1, mt + 1, rt, ql, qr, add);
}
else {
update(id << 1, lt, mt, ql, mt, add);
update(id << 1 | 1, mt + 1, rt, mt + 1, qr, add);
}
tree[id] = min(tree[id << 1], tree[id << 1 | 1]);
}
bool check(int sz, int lim) {
int n = N - sz + 1;
int m = M - sz + 1;
cnt_x[1] = 1;
cnt_x[n + 1] = 1;
for (int i = 2; i <= n; i++) {
cnt_x[i] = 0;
}
cnt_y[1] = 1;
cnt_y[m + 1] = 1;
for (int i = 2; i <= m; i++) {
cnt_y[i] = 0;
}
for (int pos = 1; pos <= min(K, lim); pos++) {
int i = order[pos];
int lx = max(1, Lx[i] - sz + 1);
int rx = min(n, Rx[i]);
int ly = max(1, Ly[i] - sz + 1);
int ry = min(m, Ry[i]);
if (lx <= rx && ly <= ry) {
cnt_x[lx]++;
cnt_x[rx + 1]++;
cnt_y[ly]++;
cnt_y[ry + 1]++;
}
}
int sz_x = 0;
for (int i = 1; i <= n + 1; i++) {
swap(sz_x, cnt_x[i]);
sz_x += cnt_x[i];
}
int sz_y = 0;
for (int i = 1; i <= m + 1; i++) {
swap(sz_y, cnt_y[i]);
sz_y += cnt_y[i];
}
events_x[cnt_x[1]].first = 1;
events_x[cnt_x[1]].second = 0;
cnt_x[1]++;
events_x[cnt_x[n + 1]].first = n + 1;
events_x[cnt_x[n + 1]].second = 0;
cnt_x[n + 1]++;
events_y[cnt_y[1]].first = 1;
events_y[cnt_y[1]].second = 0;
cnt_y[1]++;
events_y[cnt_y[m + 1]].first = m + 1;
events_y[cnt_y[m + 1]].second = 0;
cnt_y[m + 1]++;
for (int pos = 1; pos <= min(K, lim); pos++) {
int i = order[pos];
int lx = max(1, Lx[i] - sz + 1);
int rx = min(n, Rx[i]);
int ly = max(1, Ly[i] - sz + 1);
int ry = min(m, Ry[i]);
if (lx <= rx && ly <= ry) {
events_x[cnt_x[lx]].first = lx;
events_x[cnt_x[lx]].second = i;
cnt_x[lx]++;
events_x[cnt_x[rx + 1]].first = rx + 1;
events_x[cnt_x[rx + 1]].second = -i;
cnt_x[rx + 1]++;
events_y[cnt_y[ly]].first = ly;
events_y[cnt_y[ly]].second = i;
cnt_y[ly]++;
events_y[cnt_y[ry + 1]].first = ry + 1;
events_y[cnt_y[ry + 1]].second = -i;
cnt_y[ry + 1]++;
}
}
n = 0;
int sz_q = 0;
for (int i = 0; i < sz_x; i++) {
if (i == 0 || events_x[i].first != events_x[i - 1].first) {
if (n) {
queries[sz_q++] = 0;
}
n++;
}
int id = events_x[i].second;
if (id) {
queries[sz_q++] = id;
}
}
n--;
m = 0;
for (int i = 0; i < sz_y; i++) {
if (i == 0 || events_y[i].first != events_y[i - 1].first) {
m++;
}
int id = events_y[i].second;
if (id > 0) {
ly[id] = m;
}
else {
ry[-id] = m - 1;
}
}
m--;
reset(1, 1, m);
for (int i = 0; i < sz_q; i++) {
int id = queries[i];
if (id > 0) {
update(1, 1, m, ly[id], ry[id], cost[id]);
}
else if (id < 0) {
update(1, 1, m, ly[-id], ry[-id], -cost[-id]);
}
else if (tree[1] <= B) {
return true;
}
}
return false;
}
mt19937 gen(69420);
const int max_iters = 2;
void just_do_it() {
cin >> N >> M >> B >> K;
for (int i = 1; i <= K; i++) {
order[i] = i;
}
int lt = 1;
int rt = min(N, M);
for (int i = 1; i <= K; i++) {
cin >> Lx[i] >> Ly[i] >> Rx[i] >> Ry[i] >> cost[i];
if (cost[i] > B) {
int s1 = min(Lx[i] - 1, M);
int s2 = min(N - Rx[i], M);
int s3 = min(N, Ly[i] - 1);
int s4 = min(N, M - Ry[i]);
rt = min(rt, max(max(max(s1, s2), s3), s4));
}
}
int res = rt;
int lim = 10000;
for (int iter = 0; iter < max_iters; iter++) {
if (iter == max_iters - 1) {
lim = K;
}
shuffle(order + 1, order + K + 1, gen);
lt = 1;
rt = res;
res = 0;
while (lt <= rt) {
int mt = (lt + rt) >> 1;
if (check(mt, lim)) {
res = mt;
lt = mt + 1;
}
else {
rt = mt - 1;
}
}
}
cout << res;
}
Compilation message
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
from /usr/include/c++/10/ext/atomicity.h:35,
from /usr/include/c++/10/bits/ios_base.h:39,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from pyramid_base.cpp:4:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'tune=native' was already specified in 'target' attribute
73 | _GLIBCXX_GTHRW(rwlock_rdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'tune=native' was already specified in 'target' attribute
74 | _GLIBCXX_GTHRW(rwlock_tryrdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'tune=native' was already specified in 'target' attribute
75 | _GLIBCXX_GTHRW(rwlock_wrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'tune=native' was already specified in 'target' attribute
76 | _GLIBCXX_GTHRW(rwlock_trywrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'tune=native' was already specified in 'target' attribute
77 | _GLIBCXX_GTHRW(rwlock_unlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'tune=native' was already specified in 'target' attribute
91 | __gthrw(pthread_rwlock_timedrdlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'tune=native' was already specified in 'target' attribute
101 | __gthrw(pthread_rwlock_timedwrlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'tune=native' was already specified in 'target' attribute
