/*
ID: USACO_template
LANG: C++
PROG: https://oj.uz/problem/view/IOI08_pyramid_base
*/
#include <iostream> //cin , cout
#include <fstream> //fin, fout
#include <stdio.h> // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack> // stacks
#include <queue> // queues
#include <map>
#include <string>
#include <string.h>
#include <set>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi; /// adjlist without weight
typedef vector<pii> vii; /// adjlist with weight
typedef vector<pair<int,pii>> vpip; /// edge with weight
typedef long long ll;
#define mp make_pair
#define ff first
#define ss second
#define pb push_back
#define sz(x) (int)(x).size()
#define adjread {int a, b; cin >> a >> b; adjlist[a].pb(b); adjlist[b].pb(a); }
const int MOD = 1e9+7; // 998244353;
const int MX = 2e5+5; //
const ll INF = 1e18; //
#define MAXV 100007
#define MAXE 100007
const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
int x, y, ypar;
int type;
int c;
bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
vector<NODE> p0, p;
vi ylist;
map<int, int> y2i;
int i2y[MAXV*2];
bool debug;
int M, N, B, ctP;
/// ------ Segment Treee --------
int Nseg[2];
struct SEGNODE {
ll mi; /// mx is always updated before lazy value is used.
int lzVal;
bool LazyPushedDown; /// flag whether we already pushed down the lazy additional value
};
SEGNODE seg[1<<19]; /// max 2e5 unique y, which needs 2^19 for Nseg
void pullUp(int v, int l, int m, int r) {
if(l==r) return;
seg[v].mi = min(seg[2*v].mi, seg[2*v+1].mi);
}
void pushDown(int v, int l, int m, int r) {
if(l==r) {
seg[v].LazyPushedDown = true;
return;
}
if(seg[v].LazyPushedDown) return;
/// push down
int u = 2*v;
seg[u].mi += seg[v].lzVal;
seg[u].lzVal += seg[v].lzVal;
seg[u].LazyPushedDown = false;
if(debug) cout << " .. .. push down to " << l << "," << m << " = " << seg[u].mi << " at node " << u << endl;
u = 2*v + 1;
seg[u].mi += seg[v].lzVal;
seg[u].lzVal += seg[v].lzVal;
seg[u].LazyPushedDown = false;
if(debug) cout << " .. .. push down to " << m+1 << "," << r << " = " << seg[u].mi << " at node " << u << endl;
/// update v
seg[v].lzVal = 0;
seg[v].LazyPushedDown = true;
}
void buildSeg(int v = 1, int l = Nseg[0], int r = Nseg[1]) {
//if(debug) cout << l << " " << r << endl;
if(l == r) { // leaf
seg[v].mi = 0;
seg[v].lzVal = 0; seg[v].LazyPushedDown = true;
return;
}
int mid = (l + r) / 2;
buildSeg(2*v, l, mid); buildSeg(2*v+1, mid+1, r);
seg[v].mi = 0;
seg[v].lzVal = 0; seg[v].LazyPushedDown = true;
}
void initSeg() {
/// build a segment tree for array of interest indexed from Nseg[0] to Nseg[1]
Nseg[0] = 0;
Nseg[1] = sz(ylist)-1;
buildSeg();
}
void updateSeg(int ule, int uri, int val, int v = 1, int l = Nseg[0], int r = Nseg[1]){
if(l > r) return;
if(r < ule || l > uri) return;
if(l == r) {
seg[v].mi += val;
seg[v].LazyPushedDown = true;
if(debug) cout << " .. .. seg " << l << "," << r << " = " << seg[v].mi << endl;
return;
}
int mid = (l + r) / 2;
if(ule <= l && r <= uri) {
pushDown(v, l, mid, r);
seg[v].mi += val;
seg[v].lzVal += val;
seg[v].LazyPushedDown = false;
if(debug) cout << " .. .. seg " << l << "," << r << " = " << seg[v].mi << endl;
return;
}
pushDown(v, l, mid, r);
updateSeg(ule, uri, val, 2*v, l, mid);
updateSeg(ule, uri, val, 2*v+1, mid+1, r);
pullUp(v, l, mid, r);
if(debug) cout << " .. .. seg " << l << "," << r << " = " << seg[v].mi << endl;
}
int querySeg(int qle, int qri, int v = 1, int l = Nseg[0], int r = Nseg[1]) {
if(r < qle || l > qri) return MOD;
if(qle <= l && r <= qri) {
return seg[v].mi;
}
int mid = (l + r) / 2;
pushDown(v, l, mid, r);
int rect = min(querySeg(qle, qri, 2*v, l, mid), querySeg(qle, qri, 2*v+1, mid+1, r));
pullUp(v, l, mid, r);
return rect;
}
int main() {
debug = false;
ios_base::sync_with_stdio(false); cin.tie(0);
int i, j, k;
cin >> M >> N >> B >> ctP;
for(i=0;i<ctP;i++) {
int x1, y1, x2, y2, c; cin >> x1 >> y1 >> x2 >> y2 >> c;
if(x1>x2) swap(x1,x2);
if(y1>y2) swap(y1, y2);
x2++; //y2++;
p0.pb((NODE){x1, y1, y2, 0, c});
p0.pb((NODE){x2, y2, y1, 1, c});
}
int ans = 0, lo, hi;
lo = 0; hi = min(M, N);
while(lo <= hi) {
int mid = (lo+hi)/2;
if(debug) cout << endl << "working on size = " << mid << endl;
/// expand each rect to left/bottom by box size
p.clear(); ylist.clear();
for(NODE v : p0) {
if(v.type == 0) {
v.x = max(1, v.x - mid + 1);
v.y = max(1, v.y - mid + 1);
} else {
v.ypar = max(1, v.ypar - mid +1);
}
p.pb(v);
ylist.pb(v.y); ylist.pb(v.ypar);
}
/// compress y
sort(p.begin(), p.end());
sort(ylist.begin(), ylist.end());
ylist.erase(unique(ylist.begin(), ylist.end()), ylist.end());
for(i=0;i<sz(ylist);i++) {
y2i[ylist[i]] = i; i2y[i] = ylist[i];
if(debug) cout << ylist[i] << " ";
if(debug && i == sz(ylist)-1) cout << endl;
}
/// init seg
initSeg();
/// cal
bool ok = false;
i = sz(p) -1;
if( (M - p[i].x+1) >= mid && N >= mid ) {
ok = true;
} else {
auto it = upper_bound(ylist.begin(), ylist.end(), N-mid+1);
int r1 = (it - ylist.begin()) -1;
r1 = max(0, r1);
if(debug) cout << " .. query range to " << r1 << endl;
int pre_x = p[0].x;
for(i =0; i<sz(p); i++) {
NODE v = p[i];
if(v.x + mid > M) { break;}
if(i >0 && v.x != p[i-1].x) {
int b0 = querySeg(0, r1);
if(b0 <= B) {
ok = true;
if(debug) cout <<" at " << v.x << " size " << mid << " ok" << endl;
break; /// can make a rect with size of mid
}
pre_x = v.x;
}
if(debug) cout << "work on " << v.x << ", " << v.y << " for " << v.c << endl;
if(v.type==0) {
j = y2i[v.y]; k = y2i[v.ypar];
updateSeg(j, k, v.c);
if(debug) cout << " .. update range " << v.y << ", " << v.ypar << " add cost of " << v.c << " and min= " << querySeg(0, r1) << endl;
} else {
j = y2i[v.ypar]; k = y2i[v.y];
updateSeg(j, k, -v.c);
if(debug) cout << " .. erase range " << v.ypar << ", " << v.y << " and min cost = " << querySeg(0, r1) << endl;
}
}
}
/// next step
if(ok) {
ans = max(ans, mid);
lo=mid+1;
if(debug) cout << "-> size = " << ans << " OK. next " << lo << "," << hi << endl;
} else {
hi = mid -1;
if(debug) cout << "-> size = " << ans << " NOK. next " << lo << "," << hi << endl;
}
}
if(debug) cout << endl << "EOL" << endl;
cout << ans << endl;
}
Compilation message
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:222:17: warning: variable 'pre_x' set but not used [-Wunused-but-set-variable]
222 | int pre_x = p[0].x;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
1144 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
1400 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
1576 KB |
Output is correct |
| 2 |
Correct |
164 ms |
1704 KB |
Output is correct |
| 3 |
Correct |
121 ms |
1752 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
573 ms |
6600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
803 ms |
10960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1280 ms |
16716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1222 ms |
14132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
301 ms |
67128 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
432 ms |
100064 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
555 ms |
118968 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
