#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAXT = 1050;
vector<lint> cy;
struct node {
lint cmin, cmax, gap;
node() {
cmin = 1e18;
cmax = -1e18;
gap = 0;
}
node(lint pos) {
cmin = cmax = pos;
gap = 0;
}
node(lint fuck1, lint fuck2, lint fuck3) {
cmin = fuck1;
cmax = fuck2;
gap = fuck3;
}
node operator+(const node &nd) {
if (cmin < 0)
return nd;
if (nd.cmin < 0)
return *this;
return node(min(cmin, nd.cmin), max(cmax, nd.cmax), max({gap, nd.gap, nd.cmin - cmax - 1}));
}
};
struct seg {
node tree[MAXT];
int lim;
void init(int sz) {
for (lim = 1; lim <= sz; lim <<= 1)
;
fill(tree, tree + MAXT, node());
}
void upd(int x, int cnt) {
if (cnt == 0)
tree[x + lim] = node();
else
tree[x + lim] = node(cy[x]);
x += lim;
while (x > 1) {
x >>= 1;
tree[x] = tree[2 * x] + tree[2 * x + 1];
}
}
} seg;
int cnt[1557];
lint sumFixed(lint r, lint c, lint g, vector<pi> a) {
vector<array<lint, 3>> e1, e2, event;
e1.push_back({0, -1, 0});
for (auto &[x, y] : a) {
e1.push_back({x, y, +1});
e2.push_back({x + 1 + g, y, -1});
}
e2.push_back({r + g, -1, 0});
event.resize(sz(e1) + sz(e2));
merge(all(e1), all(e2), event.begin());
vector<array<lint, 5>> chop;
for (int i = 0; i < sz(event);) {
int j = i;
while (j < sz(event) && event[i][0] == event[j][0]) {
if (event[j][2]) {
cnt[event[j][1]] += event[j][2];
seg.upd(event[j][1], cnt[event[j][1]]);
}
j++;
}
if (j == sz(event))
break;
lint lmax = seg.tree[1].cmin, rmax = c - 1 - seg.tree[1].cmax, lrmax = seg.tree[1].gap;
chop.push_back({event[i][0], event[j][0], lmax, rmax, lrmax});
i = j;
}
int k = 0;
priority_queue<pi> pq1, pq2, pq3;
lint ans = 1e18;
for (int i = 0; i < sz(chop); i++) {
if (chop[i][0] > g)
break;
while (k < sz(chop) && chop[k][0] < chop[i][0] + r) {
pq1.push({chop[k][2], chop[k][1]});
pq2.push({chop[k][3], chop[k][1]});
pq3.push({chop[k][4], chop[k][1]});
k++;
}
while (sz(pq1) && pq1.top()[1] <= chop[i][0])
pq1.pop();
while (sz(pq2) && pq2.top()[1] <= chop[i][0])
pq2.pop();
while (sz(pq3) && pq3.top()[1] <= chop[i][0])
pq3.pop();
ans = min(ans, max(pq1.top()[0] + pq2.top()[0], pq3.top()[0]));
}
return ans;
}
map<pi, lint> mp;
// abandon
lint solve(lint r, lint c, lint dl, lint dr, vector<pi> a) {
if (mp.count({dl, dr}))
return mp[pi{dl, dr}];
vector<array<lint, 3>> e1, e2, event;
for (auto &[x, y] : a) {
int l = max(0ll, x - dl);
int e = min(r * 1ll, x + 1 + dr);
e1.push_back({l, y, +1});
e2.push_back({e, y, -1});
}
event.resize(sz(e1) + sz(e2));
merge(all(e1), all(e2), event.begin());
if (event[0][0] != 0 || event.back()[0] != r)
return mp[pi{dl, dr}] = 1e18;
lint lmax = 0, rmax = 0, lrmax = 0;
multiset<lint> s;
for (int i = 0; i < sz(event);) {
int j = i;
while (j < sz(event) && event[i][0] == event[j][0]) {
if (event[j][2]) {
cnt[event[j][1]] += event[j][2];
seg.upd(event[j][1], cnt[event[j][1]]);
}
j++;
}
if (j == sz(event))
break;
lmax = max(lmax, seg.tree[1].cmin);
rmax = max(rmax, c - 1 - seg.tree[1].cmax);
lrmax = max(lrmax, seg.tree[1].gap);
i = j;
}
return mp[pi{dl, dr}] = max(lmax + rmax, lrmax);
}
// n^3 log n
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, r, c;
cin >> r >> c >> n;
vector<pi> a(n);
for (auto &[x, y] : a)
cin >> x >> y, x--, y--;
sort(all(a));
lint ans = 1e18;
vector<lint> gaps = {0};
for (int i = 0; i < n; i++) {
cy.push_back(a[i][1]);
for (int j = i + 1; j < n; j++) {
if (a[j][0] > a[i][0])
gaps.push_back(a[j][0] - a[i][0] - 1);
}
}
sort(all(cy));
cy.resize(unique(all(cy)) - cy.begin());
for (int i = 0; i < n; i++) {
a[i][1] = lower_bound(all(cy), a[i][1]) - cy.begin();
}
seg.init(sz(cy));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
ans = min(ans, a[i][0] + r - 1 - a[j][0] + solve(r, c, a[i][0], r - 1 - a[j][0], a));
}
}
sort(all(gaps));
gaps.resize(unique(all(gaps)) - gaps.begin());
for (auto &dy : gaps) {
if (ans > dy)
ans = min(ans, sumFixed(r, c, dy, a) + dy);
}
cout << ans << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
