#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
//~ #define int ll
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
int n, m; cin >> n >> m;
int sz; cin >> sz;
vector<int> x(sz), y(sz), t;
for(int i=0;i<sz;i++){
cin >> x[i] >> y[i];
}
//~ assert(sz <= 1);
t = x;
sort(t.begin(), t.end());
t.erase(unique(t.begin(), t.end()), t.end());
vector<int> used(t.size());
vector<int> id(sz);
for(int i=0;i<sz;i++){
id[i] = lower_bound(t.begin(), t.end(), x[i]) - t.begin() + 1;
}
ll res = 2 * (n + m);
auto check = [&](int d){
vector<ar<ll, 2>> tot;
for(int i=0;i<sz;i++){
tot.push_back({y[i], id[i]});
tot.push_back({y[i] + d + 1, -id[i]});
}
sort(tot.begin(), tot.end());
vector<ll> v;
vector<int> is;
vector<ar<int, 3>> Mn;
multiset<int> mn, used;
mn.insert(0);
auto add = [&](int x){
if(used.empty()){
used.insert(x);
return;
}
auto it = used.upper_bound(x);
if(it == used.begin()){
mn.insert(*it - x - 1);
used.insert(x);
return;
}
if(it == used.end()){
it--;
mn.insert(x - *it - 1);
used.insert(x);
return;
}
auto l = it; l--;
mn.erase(mn.find(*it - *l - 1));
mn.insert(*it - x - 1);
mn.insert(x - *l - 1);
used.insert(x);
};
auto del = [&](int x){
used.erase(used.find(x));
if(used.empty()) return;
auto it = used.upper_bound(x);
if(it == used.begin()){
mn.erase(mn.find(*it - x - 1));
return;
}
if(it == used.end()){
it--;
mn.erase(mn.find(x - *it - 1));
return;
}
auto l = it; l--;
mn.erase(mn.find(*it - x - 1));
mn.erase(mn.find(x - *l - 1));
mn.insert(*it - *l - 1);
};
for(int i=0;i<(int)tot.size();){
int j = i;
while(j < (int)tot.size() && tot[j][0] == tot[i][0]){
if(tot[j][1] > 0) add(t[tot[j][1] - 1]);
else del(t[-tot[j][1] - 1]);
j++;
}
v.push_back(tot[i][0]);
if(used.empty()){
Mn.push_back({0, 0, 0});
is.push_back(1);
} else {
assert(!mn.empty());
Mn.push_back({*used.begin() - 1, n - *--used.end(), *--mn.end()});
is.push_back(0);
}
i = j;
}
//~ cout<<d<<"\n";
//~ for(int i=0;i<(int)v.size();i++){
//~ cout<<v[i]<<" ";
//~ } cout<<"\n";
//~ for(int i=0;i<(int)v.size();i++){
//~ cout<<is[i]<<" ";
//~ } cout<<"\n";
//~ for(int i=0;i<(int)v.size();i++){
//~ cout<<Mn[i][0]<<" ";
//~ } cout<<"\n";
//~ for(int i=0;i<(int)v.size();i++){
//~ cout<<Mn[i][1]<<" ";
//~ } cout<<"\n";
//~ for(int i=0;i<(int)v.size();i++){
//~ cout<<Mn[i][2]<<" ";
//~ } cout<<"\n";
set<int> mnl, mnr;
mn.clear();
int r = 0, cnt = 0;
for(int i=0;i + 1 < (int)v.size();i++){
while(r < (int)v.size() && v[r] - v[i] < m){
mn.insert(Mn[r][2]);
mnl.insert(Mn[r][0]);
mnr.insert(Mn[r][1]);
cnt += is[r];
r++;
}
if(cnt == 0){
res = min(res, 1ll * d + max(*--mn.end(), *--mnl.end() + *--mnr.end()));
}
mn.erase(mn.find(Mn[i][2]));
mnl.erase(mnl.find(Mn[i][0]));
mnr.erase(mnr.find(Mn[i][1]));
cnt -= is[i];
}
};
//~ check(4);
for(int i=0;i<sz;i++){
for(int j=0;j<sz;j++){
check(y[i] - 1 + m - y[j]);
}
for(int k=0;k<sz;k++){
if(y[i] >= y[k]) continue;
check(y[k] - y[i] - 1);
}
}
cout<<res<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
