#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=2e9+7;
const int LIM=307;
pair<ll,ll>T[LIM];
ll R, C, n;
vector<pair<ll,ll>>Ci, Di, Ei;
ll solveab(ll a, ll b) {
ll c=0, d=0, cpd=0, lst=1;
ll po=0, ko=Ci.size()-1;
while(po<ko) {
ll sr=(po+ko)/2;
if(Ci[sr].st>b) po=sr+1; else ko=sr;
}
c=Ci[po].nd;
po=0; ko=Di.size()-1;
while(po<ko) {
ll sr=(po+ko)/2;
if(Di[sr].st>b) po=sr+1; else ko=sr;
}
d=Di[po].nd;
po=0; ko=Ei.size()-1;
while(po<ko) {
ll sr=(po+ko)/2;
if(Ei[sr].st<b) po=sr+1; else ko=sr;
}
cpd=max(Ei[po].nd, 0ll);
set<pair<ll,ll>>A;
multiset<ll>B;
vector<pair<ll,ll>>V;
vector<ll>odw(n);
rep(i, n) V.pb({max(1ll, T[i].st-a), i});
rep(i, n) V.pb({min(R+1, T[i].st+b+1), i});
sort(all(V));
for(auto i : V) {
if(i.st!=lst) {
if(B.size()) {
auto it=B.end(); --it;
ll p=*it;
cpd=max(cpd, p);
}
lst=i.st;
}
if(!odw[i.nd]) {
odw[i.nd]=1;
if(A.size()) {
ll lewo=0, prawo=C+1;
auto it=A.lower_bound({T[i.nd].nd, i.nd});
if(it!=A.end()) {
auto p=*it;
prawo=p.st;
}
if(it!=A.begin()) {
--it;
auto p=*it;
lewo=p.st;
}
if(lewo!=0 && prawo!=C+1) B.erase(B.find(prawo-lewo-1));
if(lewo!=0) B.insert(T[i.nd].nd-lewo-1);
if(prawo!=C+1) B.insert(prawo-T[i.nd].nd-1);
}
A.insert({T[i.nd].nd, i.nd});
} else {
A.erase({T[i.nd].nd, i.nd});
if(A.size()) {
ll lewo=0, prawo=C+1;
auto it=A.lower_bound({T[i.nd].nd, i.nd});
if(it!=A.end()) {
auto p=*it;
prawo=p.st;
}
if(it!=A.begin()) {
--it;
auto p=*it;
lewo=p.st;
}
if(lewo!=0 && prawo!=C+1) B.insert(prawo-lewo-1);
if(lewo!=0) B.erase(B.find(T[i.nd].nd-lewo-1));
if(prawo!=C+1) B.erase(B.find(prawo-T[i.nd].nd-1));
}
}
}
return a+b+max(c+d, cpd);
}
ll solvea(ll a) {
Ci.clear(); Di.clear(); Ei.clear();
vector<pair<ll,ll>>P;
rep(i, n) P.pb({T[i].nd, i});
sort(all(P));
rep(i, n) {
vector<pair<ll,ll>>Q;
rep(j, i+1) Q.pb({max(1ll, T[P[j].nd].st-a), T[P[j].nd].st});
sort(all(Q));
ll ma=1, mi=0;
for(auto j : Q) {
mi=max(mi, j.st-ma-1);
ma=max(ma, j.nd);
}
mi=max(mi, R-ma);
if(Q[0].st!=1) mi=INF;
Ci.pb({mi, P[i].st-1});
}
rep(i, n) {
vector<pair<ll,ll>>Q;
rep(j, i+1) Q.pb({max(1ll, T[P[n-j-1].nd].st-a), T[P[n-j-1].nd].st});
sort(all(Q));
ll ma=1, mi=0;
for(auto j : Q) {
mi=max(mi, j.st-ma-1);
ma=max(ma, j.nd);
}
mi=max(mi, R-ma);
if(Q[0].st!=1) mi=INF;
Di.pb({mi, C-P[n-i-1].st});
}
rep(xd, 2) {
rep(j, n) rep(i, j) {
if(T[P[i].nd].st<=T[P[j].nd].st) {
ll mi=INF, ma=0;
for(int l=i+1; l<j; ++l) {
if(T[P[l].nd].st>=T[P[i].nd].st) mi=min(mi, T[P[l].nd].st-a);
if(T[P[l].nd].st-a<=T[P[j].nd].st) ma=max(ma, T[P[l].nd].st);
}
if(mi==INF || ma==0) Ei.pb({INF, abs(P[i].st-P[j].st)-1});
else if(mi<=T[P[j].nd].st || ma>=T[P[i].nd].st) Ei.pb({0, abs(P[i].st-P[j].st)-1});
else Ei.pb({mi-ma-1, abs(P[i].st-P[j].st)-1});
}
}
reverse(all(P));
}
sort(all(Ei));
for(int i=Ei.size()-2; i>=0; --i) Ei[i].nd=max(Ei[i].nd, Ei[i+1].nd);
vector<ll>A;
rep(i, n) A.pb(T[i].st);
sort(all(A));
ll b=R-A[n-1], apb=0;
rep(i, n-1) apb=max(apb, A[i+1]-A[i]-1);
ll ans=INF;
rep(i, n) {
ll x=R-T[i].st;
if(x>=b && a+x>=apb) ans=min(ans, solveab(a, x));
}
rep(i, n) rep(j, i) {
ll x=abs(T[i].st-T[j].st)-1;
if(x==-1 || x<apb) continue;
ll y=x-a;
if(y>=b) ans=min(ans, solveab(a, y));
}
return ans;
}
ll solve() {
ll ans=INF;
rep(i, n) ans=min(ans, solvea(T[i].st-1));
return ans;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> R >> C >> n;
rep(i, n) cin >> T[i].st >> T[i].nd;
ll ans=INF;
rep(i, 4) {
ans=min(ans, solve());
rep(j, n) T[j]={C-T[j].nd+1, T[j].st};
swap(R, C);
}
cout << ans << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
468 KB |
Output is correct |
| 2 |
Correct |
60 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
71 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
468 KB |
Output is correct |
| 2 |
Correct |
60 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
71 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Runtime error |
0 ms |
348 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
