#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
ll rand_int(ll l, ll r) { //[l, r]
#ifdef LOCAL
static mt19937_64 gen;
#else
static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
#endif
return uniform_int_distribution<ll>(l, r)(gen);
}
template <uint MD> struct ModInt {
using M = ModInt;
const static M G;
uint v;
ModInt(ll _v = 0) { set_v(_v % MD + MD); }
M& set_v(uint _v) {
v = (_v < MD) ? _v : _v - MD;
return *this;
}
explicit operator bool() const { return v != 0; }
M operator-() const { return M() - *this; }
M operator+(const M& r) const { return M().set_v(v + r.v); }
M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
M operator/(const M& r) const { return *this * r.inv(); }
M& operator+=(const M& r) { return *this = *this + r; }
M& operator-=(const M& r) { return *this = *this - r; }
M& operator*=(const M& r) { return *this = *this * r; }
M& operator/=(const M& r) { return *this = *this / r; }
bool operator==(const M& r) const { return v == r.v; }
M pow(ll n) const {
M x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
M inv() const { return pow(MD - 2); }
friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
using Mint = ModInt<998244353>;
template<> const Mint Mint::G = Mint(3);
using t4 = tuple<int,int,int,int>;
int H, W, n;
int res=2e9;
void Solve(){
scanf("%d%d",&H,&W);
scanf("%d",&n);
vc<pii>w(n);
set<int>SX, SY;
rep(i,n){
scanf("%d%d",&w[i].fi,&w[i].se);
SX.insert(w[i].fi);SX.insert(w[i].fi+H);
SY.insert(w[i].se);SY.insert(w[i].se+W);
}
vi X, Y;
for(auto &t: SX)X.pb(t);
for(auto &t: SY)Y.pb(t);
rep(i,n){
w[i].fi = lower_bound(all(X), w[i].fi) - X.begin();
w[i].se = lower_bound(all(Y), w[i].se) - Y.begin();
}
vi DX, DY;
rep(i,si(X)){
rng(j,i+1,si(X)-1)DX.pb(X[j]-X[i]);
}
rep(i,si(Y)){
rng(j,i+1,si(Y)-1)DY.pb(Y[j]-Y[i]);
}
sort(all(DX));
DX.resize(unique(all(DX)) - DX.begin());
sort(all(DY));
DY.resize(unique(all(DY)) - DY.begin());
int nX = si(X), nY = si(Y);
vi PX(n), PY(n);
vc<vi> S(nX,vi(nY));
rep(i,n){
PX[i] = w[i].fi;
PY[i] = nY-1;
}
vc<priority_queue<int>>PQ1(nX), PQ2(nX);
int mY = lower_bound(all(Y),W) - Y.begin();
auto add0 = [&](int x, int y){
if(y<=mY) PQ1[x].push(y);
else PQ2[x].push(-y);
};
auto getLeft = [&](int x){
while(!PQ1[x].empty()){
int y = PQ1[x].top();
if(!S[x][y])return y;
PQ1[x].pop();
}
return 0;
};
auto getRight = [&](int x){
while(!PQ2[x].empty()){
int y = -PQ2[x].top();
if(!S[x][y])return y;
PQ2[x].pop();
}
return nY;
};
int ans = 2e9;
rng(i,1,nX-1){
rng(j,1,nY-1){
add0(i,j);
}
}
vi LL(nX), RR(nX), dL(nX), dR(nX);
int pdy = si(DY)-1, dy = DY.back();
for(auto &dx : DX){
rep(i,n){
int bx = w[i].fi;
int by = w[i].se;
while(PX[i] < nX - 1 && X[PX[i]+1] - X[bx] <= dx){
PX[i]++;
rng(j,by+1,PY[i]){
S[PX[i]][j]++;
}
}
}
while(1){
/* printf("! %d %d\n",dx,dy);
rng(i,1,nX-1){
rng(j,1,nY-1){
printf("%d",S[i][j]);
}
puts("");
}*/
rng(i,1,nX-1){
LL[i] = getLeft(i);
RR[i] = getRight(i);
if(LL[i]==mY)RR[i]=mY;
RR[i]--;
//printf("%d: %d %d\n",X[i],Y[LL[i]],Y[RR[i]]);
}
int hL=1, tL=0;
int hR=1, tR=0, CK=0;
rng(i,1,nX-1){
while(hL <= tL && X[i] - X[dL[hL]] >= H)hL++;
while(hL <= tL && LL[dL[tL]] <= LL[i])tL--;
dL[++tL] = i;
int l = LL[dL[hL]];
while(hR <= tR && X[i] - X[dR[hR]] >= H)hR++;
while(hR <= tR && RR[dR[tR]] >= RR[i])tR--;
dR[++tR] = i;
int r = RR[dR[hR]];
if(X[i]-X[0] >= H && Y[r]-Y[l] >= W){
//printf("%d %d %d %d\n",dx,dy,Y[l],Y[r]);
ans = min(ans, dx+dy-2);
CK=1;
break;
}
}
if(!CK)break;
pdy--;
if(pdy<0)break;
dy = DY[pdy];
rep(i,n){
int bx = w[i].fi;
int by = w[i].se;
while(Y[PY[i]] - Y[by] > dy){
rng(j,bx+1,PX[i]){
S[j][PY[i]]--;
if(!S[j][PY[i]])add0(j,PY[i]);
}
PY[i]--;
}
}
}
if(pdy<0)break;
}
printf("%d\n",ans);
}
int main(){
int TC=1;
while(TC--){
Solve();
}
}
Compilation message
cultivation.cpp: In function 'void Solve()':
cultivation.cpp:79:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
79 | scanf("%d%d",&H,&W);
| ~~~~~^~~~~~~~~~~~~~
cultivation.cpp:80:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
80 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
cultivation.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
84 | scanf("%d%d",&w[i].fi,&w[i].se);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
440 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
440 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
2 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
1 ms |
348 KB |
Output is correct |
| 7 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
