#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;
const int SZ = 1024;
struct Tree{
int Mn[SZ+SZ], K[SZ+SZ];
void UDT(int nd){
Mn[nd] = min(Mn[nd*2],Mn[nd*2+1]);
}
void Add2(int nd, int k){
Mn[nd] += k;
K[nd] += k;
}
void Spread(int nd){
Add2(nd*2, K[nd]);
Add2(nd*2+1, K[nd]);
K[nd]=0;
}
void init(int nd, int b, int e){
K[nd]=0;
if(b==e){
Mn[nd]=0;
return;
}
int m = (b+e)>>1;
init(nd*2,b,m);
init(nd*2+1,m+1,e);
UDT(nd);
}
void Add(int nd, int b, int e, int s, int l, int x){
if(s>l)return;
if(s<=b&&e<=l){
Add2(nd,x);
return;
}
Spread(nd);
int m = (b+e)>>1;
if(s<=m)Add(nd*2,b,m,s,l,x);
if(l>m)Add(nd*2+1,m+1,e,s,l,x);
UDT(nd);
}
int getLeft(int nd, int b, int e, int x){
if(Mn[nd])return SZ;
if(b==e)return b;
Spread(nd);
int m = (b+e)>>1;
if(x<=m)return getLeft(nd*2,b,m,x);
int r = getLeft(nd*2+1,m+1,e,x);
if(r==SZ)r = getLeft(nd*2,b,m,x);
return r;
}
int getRight(int nd, int b, int e, int x){
if(Mn[nd])return -1;
if(b==e)return b;
Spread(nd);
int m = (b+e)>>1;
if(x>m)return getRight(nd*2+1,m+1,e,x);
int r = getRight(nd*2,b,m,x);
if(r==-1)r = getRight(nd*2+1,m+1,e,x);
return r;
}
}IT;
struct IdxTree{
int IT[SZ+SZ];
void Put(int a, int b){
a+=SZ;
IT[a]=b;
while(a!=1){
a>>=1;
IT[a]=max(IT[a*2],IT[a*2+1]);
}
}
int Max(int b, int e){
b+=SZ,e+=SZ;
int r=-1e9;
while(b<=e){
r=max(r,IT[b]);
r=max(r,IT[e]);
b=(b+1)>>1,e=(e-1)>>1;
}
return r;
}
}LL, RR;
bool Pos(int x, int y, vc<pii> &w){
vc<t4>S;
vc<pii> Y;
rep(i,n){
Y.pb({w[i].se, i});
Y.pb({w[i].se+y, i+n});
}
Y.pb({W+1,2*n});
sort(all(Y));
vi RY(n*2+1), OY(n*2+2);
int cy=0;
rep(i,si(Y)){
if(i==0 || Y[i].fi!=Y[i-1].fi){
cy++;
OY[cy] = Y[i].fi;
}
RY[Y[i].se] = cy;
}
rep(i,n){
S.pb({w[i].fi, 1, RY[i], RY[i+n]});
S.pb({w[i].fi + x, -1, RY[i], RY[i+n]});
}
int my = RY[n*2];
sort(all(S));
IT.init(1,0,SZ-1);
vi U;
rep(i,si(S)){
auto [x, d, by, ey] = S[i];
IT.Add(1,0,SZ-1,by,ey-1,d);
if(i==si(S)-1 || x != get<0>(S[i+1])){
int l = IT.getLeft(1,0,SZ-1,my); l++;
int r = IT.getRight(1,0,SZ-1,my); r--;
LL.Put(si(U),l);
RR.Put(si(U),-r);
U.pb(x);
}
}
int pv = 0;
//printf("X,Y: %d %d\n",x,y);
rep(i,si(U)){
while(pv<si(U) && U[pv] - U[i] < H)pv++;
if(pv==si(U))return false;
int ll = LL.Max(i,pv-1);
int rr = -RR.Max(i,pv-1);
//printf("%d %d %d %d\n",ll,rr, OY[ll], OY[rr+1]);
if(ll<=rr && OY[rr+1] - OY[ll] >= W)return true;
}
return false;
}
void Solve(){
scanf("%d%d",&H,&W);
scanf("%d",&n);
vc<pii>w(n);
rep(i,n){
scanf("%d%d",&w[i].fi,&w[i].se);
}
set<int>SX, SY;
/* rep(i,n){
rep(j,n){
SX.insert(abs(w[i].fi-w[j].fi));
SY.insert(abs(w[i].se-w[j].se));
}
}
SX.erase(0);SY.erase(0);
SX.insert(H);SY.insert(W);*/
rng(i,1,H)SX.insert(i);
rng(i,1,W)SY.insert(i);
vi X, Y;
for(auto &t: SX)X.pb(t);
for(auto &t: SY)Y.pb(t);
int p1 = 0, p2 = si(Y)-1, res=2e9;
/* for(auto &x : X)printf("%d ",x);
puts("");
for(auto &y : Y)printf("%d ",y);
puts("");*/
while(p1 < si(X) && p2 >= 0){
//printf("%d %d\n",X[p1],Y[p2]);
if(Pos(X[p1],Y[p2],w)){
//printf("%d %d\n",X[p1],Y[p2]);
res = min(res, X[p1]+Y[p2]-2);
p2--;
}
else p1++;
}
printf("%d\n",res);
}
int main(){
int TC=1;
while(TC--){
Solve();
}
}
Compilation message
cultivation.cpp: In function 'void Solve()':
cultivation.cpp:213:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
213 | scanf("%d%d",&H,&W);
| ~~~~~^~~~~~~~~~~~~~
cultivation.cpp:214:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
214 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
cultivation.cpp:217:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
217 | scanf("%d%d",&w[i].fi,&w[i].se);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1154 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1154 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
