#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Point{
ll x, y;
Point(){}
Point(ll x, ll y): x(x), y(y){}
bool operator<(const Point &r)const{
return make_pair(x, y) < make_pair(r.x, r.y);
}
};
struct Query{
ll x, y; bool in;
Query(){}
Query(ll x, ll y, bool in): x(x), y(y), in(in){}
bool operator<(const Query &r)const{
if(x!=r.x) return x<r.x;
return in<r.in;
}
};
struct State{
ll x, l, r, mid;
State(){}
State(ll x, ll l, ll r, ll mid): x(x), l(l), r(r), mid(mid){}
};
ll n, m; int k;
Point arr[302];
ll ans = LLONG_MAX;
ll maxDiff;
void testInterval(ll d){
multiset<ll> mst;
multiset<ll> diff;
mst.insert(0);
mst.insert(m+1);
diff.insert(m+1);
vector<Query> vec;
for(int i=1; i<=k; i++){
vec.push_back(Query(arr[i].x, arr[i].y, 1));
vec.push_back(Query(arr[i].x+d+1, arr[i].y, 0));
}
sort(vec.begin(), vec.end());
vector<State> st;
for(int i=0; i<(int)vec.size(); i++){
if(vec[i].in == 1){
auto it = mst.lower_bound(vec[i].y);
diff.erase(diff.find(*it - *prev(it)));
diff.insert(*it - vec[i].y);
diff.insert(vec[i].y - *prev(it));
mst.insert(vec[i].y);
}
else{
auto it = mst.lower_bound(vec[i].y);
diff.erase(diff.find(*next(it) - vec[i].y));
diff.erase(diff.find(vec[i].y - *prev(it)));
diff.insert(*next(it) - *prev(it));
mst.erase(it);
}
if(i+1 == (int)vec.size() || vec[i].x != vec[i+1].x){
if(*diff.rbegin() == m+1) st.push_back(State(vec[i].x, 1e10, 1e10, 1e10));
else st.push_back(State(vec[i].x, *next(mst.begin()) - 1, m - *prev(prev(mst.end())),
*diff.rbegin() - 1));
}
}
// printf("diff: %lld\n", d);
for(int i=0; i<(int)st.size(); i++){
// printf("%lld: %lld %lld %lld\n", st[i].x, st[i].l, st[i].r, st[i].mid);
if(arr[1].x + d < vec[i].x) break;
int j = i;
while(j < (int)st.size()-1 && st[j+1].x - st[i].x < n) j++;
ll maxL = 0, maxR = 0, maxD = 0;
for(int u=i; u<=j; u++){
maxL = max(maxL, st[u].l);
maxR = max(maxR, st[u].r);
maxD = max(maxD, st[u].mid);
}
ans = min(ans, d + maxL + maxR + max(0LL, maxD - maxL - maxR));
}
}
int main(){
scanf("%lld %lld %d", &n, &m, &k);
for(int i=1; i<=k; i++){
scanf("%d %d", &arr[i].x, &arr[i].y);
}
sort(arr+1, arr+k+1);
arr[k+1].x = n+1;
for(int i=1; i<=k+1; i++) maxDiff = max(maxDiff, arr[i].x - arr[i-1].x);
testInterval(maxDiff-1);
for(int i=0; i<=k+1; i++){
for(int j=i+1; j<=k+1; j++){
if(maxDiff < arr[j].x - arr[i].x) testInterval(arr[j].x - arr[i].x - 1);
}
}
printf("%lld", ans);
}
Compilation message
cultivation.cpp: In function 'int main()':
cultivation.cpp:98:17: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
98 | scanf("%d %d", &arr[i].x, &arr[i].y);
| ~^ ~~~~~~~~~
| | |
| int* ll* {aka long long int*}
| %lld
cultivation.cpp:98:20: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'll*' {aka 'long long int*'} [-Wformat=]
98 | scanf("%d %d", &arr[i].x, &arr[i].y);
| ~^ ~~~~~~~~~
| | |
| int* ll* {aka long long int*}
| %lld
cultivation.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | scanf("%lld %lld %d", &n, &m, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
98 | scanf("%d %d", &arr[i].x, &arr[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
284 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
