#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 2e9;
ll n, m; int k;
ll X[302], Y[302];
int rx[302], ry[302], sx, sy;
ll ans = LLONG_MAX;
struct Interval{
ll l, r; /// 높이 구간
ll ldist, rdist, mdist; /// 최소 길이
Interval(){}
Interval(ll l, ll r, ll ldist, ll rdist, ll mdist): l(l), r(r), ldist(ldist), rdist(rdist), mdist(mdist){}
bool operator<(const Interval &nxt)const{
return l<nxt.l;
}
};
pair<ll, int> dqL[1002], dqR[1002], dqLen[1002];
int l1, l2, r1, r2, len1, len2;
vector<Interval> info;
ll udlength[500002], udsize;
ll A[302][302], B[302][302], C[302][302];
pair<ll, ll> arr[302];
pair<ll, ll> ableGroup(ll ud, int s, int e){
ll L = max(X[e] - ud, s==1 ? -INF : X[s-1] + 1);
ll R = min(X[s], e==k ? INF : X[e+1] - ud - 1);
if(L>R) return make_pair(-INF, -INF);
return make_pair(L, R);
}
int main(){
scanf("%lld %lld %d", &n, &m, &k);
// n=m=1000000000, k=300;
for(int i=1; i<=k; i++){
scanf("%lld %lld", &arr[i].first, &arr[i].second);
// X[i] = Y[i] = i*i+i+2;
}
sort(arr+1, arr+k+1);
for(int i=1; i<=n; i++) X[i] = arr[i].first, Y[i] = arr[i].second;
for(int i=1; i<=n; i++){
vector<ll> vec (1, Y[i]);
A[i][i] = Y[i] - 1;
B[i][i] = m - Y[i];
C[i][i] = 0;
for(int j=i+1; j<=n; j++){
auto it = lower_bound(vec.begin(), vec.end(), Y[j]);
if(!(it != vec.end() && *it == Y[j])) vec.insert(it, Y[j]);
A[i][j] = vec.front() - 1;
B[i][j] = m - vec.back();
C[i][j] = 0;
for(int k=0; k<(int)vec.size()-1; k++) C[i][j] = max(C[i][j], vec[k+1] - vec[k] - 1);
}
}
udlength[udsize++] = n-1;
for(int i=1; i<=k; i++){
udlength[udsize++] = X[i] - 1;
udlength[udsize++] = n - X[i];
for(int j=1; j<=k; j++){
if(X[i] < X[j]) udlength[udsize++] = X[j] - X[i] - 1;
udlength[udsize++] = X[i] + n - X[j] - 1;
}
}
sort(udlength, udlength+udsize);
udsize = unique(udlength, udlength+udsize) - udlength;
for(int ui=0; ui<udsize; ui++){ /// 위 - 아래 간격
ll ud = udlength[ui];
if(ud<0) continue;
bool bad = 0;
for(int i=1; i<k; i++){
if(X[i+1] - X[i] - 1 > ud) {bad = 1; break;}
}
if(bad) continue;
info.clear();
int e = 1;
for(int s=1; s<=k; s++){
while(ableGroup(ud, s, e) == make_pair(-INF, -INF)) e++;
while(1){
while(e<k && X[e]==X[e+1]) e++;
pair<ll, ll> p = ableGroup(ud, s, e);
info.push_back(Interval(p.first, p.second, A[s][e], B[s][e], C[s][e]));
if(e<n && ableGroup(ud, s, e+1) != make_pair(-INF, -INF)) e++;
else break;
}
while(s<k && X[s]==X[s+1]) s++;
while(e<=s) e++;
}
int j = 0;
l1 = l2 = r1 = r2 = len1 = len2 = 0;
dqL[l2++] = make_pair(info[0].ldist, 0);
dqR[r2++] = make_pair(info[0].rdist, 0);
dqLen[len2++] = make_pair(info[0].mdist, 0);
for(int i=0; i<(int)info.size(); i++){
if(l1!=l2 && dqL[l1].second < i) l1++;
if(r1!=r2 && dqR[r1].second < i) r1++;
if(len1!=len2 && dqLen[len1].second < i) len1++;
while(j < (int)info.size() && info[j].r - info[i].l + 1 < n){
j++;
while(l1!=l2 && dqL[l2-1].first <= info[j].ldist) l2--;
dqL[l2++] = make_pair(info[j].ldist, j);
while(r1!=r2 && dqR[r2-1].first <= info[j].rdist) r2--;
dqR[r2++] = make_pair(info[j].rdist, j);
while(len1!=len2 && dqLen[len2-1].first <= info[j].mdist) len2--;
dqLen[len2++] = make_pair(info[j].mdist, j);
}
if(j == (int)info.size()) break;
ll minL = dqL[l1].first, minR = dqR[r1].first, len = dqLen[len1].first;
ans = min(ans, ud + max(len, minL+minR));
}
}
printf("%lld", ans);
}
Compilation message
cultivation.cpp: In function 'int main()':
cultivation.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%lld %lld %d", &n, &m, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
43 | scanf("%lld %lld", &arr[i].first, &arr[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
308 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
360 KB |
Output is correct |
| 5 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
308 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
360 KB |
Output is correct |
| 5 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
308 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
360 KB |
Output is correct |
| 5 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
308 KB |
Output is correct |
| 2 |
Correct |
1 ms |
316 KB |
Output is correct |
| 3 |
Correct |
1 ms |
312 KB |
Output is correct |
| 4 |
Correct |
1 ms |
360 KB |
Output is correct |
| 5 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 6 |
Halted |
0 ms |
0 KB |
- |
