#pragma GCC optimize ("Ofast","unroll-loops")
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define MP make_pair
#define F first
#define S second
#define setpre(a) cout.precision(a),cout<<fixed;
#define ALL(a) a.begin(),a.end()
#define MEM(a,b) memset(a,b,sizeof a)
#define Tie ios::sync_with_stdio(0),cin.tie(0);
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
const int MAXN = 310;
const ll INF = 1LL << 61;
ll R, C, n, L[MAXN][MAXN], L_lim[MAXN][MAXN], R_lim[MAXN][MAXN], dis[MAXN][MAXN], ans = INF;
ll Ur[MAXN], Dr[MAXN], Ul[MAXN], Dl[MAXN];
vector<pll> v;
int main() {Tie
cin >> R >> C >> n;
v.resize(n);
ll rest = 0;
for(pll &i : v)
cin >> i.F >> i.S, rest = max(rest, i.F);
vector<pll> tv = v;
sort(ALL(tv));
ll minm = 0;
for(int i = 0; i + 1 < n; i++) {
minm = max(minm, tv[i + 1].F - tv[i].F - 1);
}
for(int i = 0; i < n; i++) {
Dl[i] = Dr[i] = Ul[i] = Ur[i] = INF;
{
ll uln = 0;
ll urn = R + 1;
ll dln = 0;
ll drn = R + 1;
for(int j = 0; j < n; j++) {
if(i == j) continue;
if(v[i].S < v[j].S) {
if(v[i].F < v[j].F) {
drn = min(drn, v[j].F);
} else if(v[i].F > v[j].F) {
dln = max(dln, v[j].F);
} else {
Dl[i] = Dr[i] = -1;
}
} else if(v[i].S > v[j].S) {
if(v[i].F < v[j].F) {
urn = min(urn, v[j].F);
} else if(v[i].F > v[j].F) {
uln = max(uln, v[j].F);
} else {
Ul[i] = Ur[i] = -1;
}
}
}
if(Dl[i] != -1) {
if(dln != 0) {
Dr[i] = drn - dln - 1;
} else {
Dr[i] = INF;
}
if(drn != R + 1) {
Dl[i] = drn - dln - 1;
} else {
Dl[i] = INF;
}
}
if(Ul[i] != -1) {
if(uln != 0) {
Ur[i] = urn - uln - 1;
} else {
Ur[i] = INF;
}
if(urn != R + 1) {
Ul[i] = urn - uln - 1;
} else {
Ul[i] = INF;
}
}
}
for(int j = i + 1; j < n; j++) {
pll x = v[i], y = v[j];
ll l = min(v[i].F, v[j].F);
ll r = max(v[i].F, v[j].F);
ll u = min(v[i].S, v[j].S);
ll d = max(v[i].S, v[j].S);
L[i][j] = r - l;
dis[i][j] = d - u - 1;
ll ln = 0;
ll rn = R + 1;
for(int k = 0; k < n; k++) {
if(u < v[k].S && v[k].S < d) {
if(l <= v[k].F && v[k].F <= r)
L_lim[i][j] = R_lim[i][j] = -1;
else if(v[k].F < l)
ln = max(ln, v[k].F);
else
rn = min(rn, v[k].F);
}
}
// if(i == 0 && j == 2)
// cout << ">>" << i << ' ' << j << ' ' << ln << ' ' << rn << '\n';
if(L_lim[i][j] == -1) continue;
if(rn != R + 1)
L_lim[i][j] = rn - ln - 1;
else
L_lim[i][j] = INF;
if(ln != 0)
R_lim[i][j] = rn - ln - 1;
else
R_lim[i][j] = INF;
}
}
vector<int> Lm, Rm(1);
for(int i = 0; i < n; i++) {
Lm.pb(v[i].F - 1);
if(R - v[i].F >= R - rest)
Rm.pb(R - v[i].F);
for(int j = i + 1; j < n; j++)
if(abs(v[i].F - v[j].F) - 1 >= R - rest)
Rm.pb(abs(v[i].F - v[j].F) - 1);
}
sort(ALL(Lm)), Lm.resize(unique(ALL(Lm)) - Lm.begin());
sort(ALL(Rm)), Rm.resize(unique(ALL(Rm)) - Rm.begin());
for(ll lm : Lm) {
map<int, int> m, dm, um;
m[0] = 1;
dm[0] = 1;
um[0] = 1;
ll dldis = 0;
ll uldis = 0;
vector<pair<ll, pll>> T;
for(int i = 0; i < n; i++) {
if(Dl[i] > lm) {
dldis = max(dldis, C - v[i].S);
}
if(Dr[i] != -1) {
dm[C - v[i].S]++;
if(Dl[i] == Dr[i] && Dr[i] != INF)
T.pb(MP(Dr[i] - lm, MP(1, C - v[i].S)));
else if(Dr[i] != INF)
T.pb(MP(Dr[i], MP(1, C - v[i].S)));
}
if(Ul[i] > lm) {
uldis = max(uldis, v[i].S - 1);
}
if(Ur[i] != -1) {
um[v[i].S - 1]++;
if(Ul[i] == Ur[i] && Ur[i] != INF)
T.pb(MP(Ur[i] - lm, MP(2, v[i].S - 1)));
else if(Ur[i] != INF)
T.pb(MP(Ur[i], MP(2, v[i].S - 1)));
}
for(int j = i + 1; j < n; j++) {
if(L_lim[i][j] <= lm) continue;
if(!dis[i][j]) continue;
if(lm < L[i][j]) {
T.pb(MP(L[i][j] - lm, MP(0, dis[i][j])));
if(L_lim[i][j] == R_lim[i][j] && R_lim[i][j] != INF)
T.pb(MP(R_lim[i][j] - lm, MP(0, -dis[i][j])));
else if(R_lim[i][j] != INF)
T.pb(MP(R_lim[i][j], MP(0, -dis[i][j])));
} else {
m[dis[i][j]]++;
if(L_lim[i][j] == R_lim[i][j] && R_lim[i][j] != INF)
T.pb(MP(R_lim[i][j] - lm, MP(0, -dis[i][j])));
else if(R_lim[i][j] != INF)
T.pb(MP(R_lim[i][j], MP(0, -dis[i][j])));
}
}
}
sort(ALL(T));
int flag = 1, top = 0;
for(int rm : Rm) {
while(top < T.size() && T[top].F <= rm) {
if(T[top].S.F == 0) {
if(T[top].S.S < 0) {
m[-T[top].S.S]--;
} else {
m[T[top].S.S]++;
}
} else if(T[top].S.F == 1) {
dm[T[top].S.S]--;
} else {
um[T[top].S.S]--;
}
top++;
}
flag = 0;
while(m.rbegin() -> S == 0) {
auto p = m.end(); p--;
m.erase(p);
}
while(dm.rbegin() -> S == 0) {
auto p = dm.end(); p--;
dm.erase(p);
}
while(um.rbegin() -> S == 0) {
auto p = um.end(); p--;
um.erase(p);
}
if(rm >= 0 && lm + rm >= minm) {
// cout << minm << '\n';
// cout << lm << ' ' << rm << ' ' << m.rbegin() -> F << ' ' << dm.rbegin() -> F << ' ' << um.rbegin() -> F << '\n';
ll tans = lm + rm + max(m.rbegin() -> F, dm.rbegin() -> F + um.rbegin() -> F);
// if(tans == 0) cout << '?' << '\n';
ans = min(ans, tans);
}
}
}
cout << ans << '\n';
}
Compilation message
cultivation.cpp: In function 'int main()':
cultivation.cpp:93:17: warning: variable 'x' set but not used [-Wunused-but-set-variable]
93 | pll x = v[i], y = v[j];
| ^
cultivation.cpp:93:27: warning: variable 'y' set but not used [-Wunused-but-set-variable]
93 | pll x = v[i], y = v[j];
| ^
cultivation.cpp:188:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
188 | while(top < T.size() && T[top].F <= rm) {
| ~~~~^~~~~~~~~~
cultivation.cpp:186:13: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
186 | int flag = 1, top = 0;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
460 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
