| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 801620 |
2023-08-02T06:58:16 Z |
박영우(#10093) |
Cultivation (JOI17_cultivation) |
C++17 |
|
7 ms |
9812 KB |
#include <bits/stdc++.h>
#include <cassert>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;
#define MAX 202020
#define MAXS 20
#define INF 2000000000000020
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
ll H, W, N;
pii arr[MAX];
ll ans = 2e9;
vector<ll> st[MAX], en[MAX];
ll U[MAX], D[MAX], UD[MAX];
bool test(ll d) {
if (d <= 0) return false;
vector<ll> ys;
ll i, j;
for (i = 1; i <= N; i++) ys.push_back(arr[i].second), ys.push_back(arr[i].second + d);
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
ll X = ys.size();
multiset<ll> ds, alls;
for (i = 0; i < X; i++) U[i] = D[i] = UD[i] = 0, st[i].clear(), en[i].clear();
for (i = 1; i <= N; i++) {
ll l, r;
l = lower_bound(ys.begin(), ys.end(), arr[i].second) - ys.begin();
r = lower_bound(ys.begin(), ys.end(), arr[i].second + d) - ys.begin();
st[l].push_back(i);
en[r].push_back(i);
}
for (i = 0; i < X; i++) {
for (auto v : st[i]) {
ll x = arr[v].first;
if (alls.size() && alls.find(x) == alls.end()) {
auto it = alls.lower_bound(x);
if (it == alls.end()) ds.insert(x - *(--it) - 1);
else if (it == alls.begin()) ds.insert(*it - x - 1);
else {
ll ne = *it;
it--;
ll pv = *it;
ds.erase(ds.find(ne - pv - 1));
ds.insert(ne - x - 1);
ds.insert(x - pv - 1);
}
}
alls.insert(x);
}
for (auto v : en[i]) {
ll x = arr[v].first;
alls.erase(alls.find(x));
if (alls.size() && alls.find(x) == alls.end()) {
auto it = alls.lower_bound(x);
if (it == alls.end()) ds.erase(ds.find(x - *(--it) - 1));
else if (it == alls.begin()) ds.erase(ds.find(*it - x - 1));
else {
ll ne = *it;
it--;
ll pv = *it;
ds.insert(ne - pv - 1);
ds.erase(ds.find(ne - x - 1));
ds.erase(ds.find(x - pv - 1));
}
}
}
if (ds.size()) UD[i] = *ds.rbegin();
if (alls.empty()) UD[i] = 2e9;
else {
U[i] = *alls.begin() - 1;
D[i] = H - *alls.rbegin();
}
}
priority_queue<pii> up, down, su;
ll mn = INF;
j = 0;
for (i = 0; i < X - 1; i++) {
up.emplace(U[i], i);
down.emplace(D[i], i);
su.emplace(UD[i], i);
while (j + 1 <= i && ys[i + 1] - ys[j + 1] >= W) j++;
while (up.size() && up.top().second < j) up.pop();
while (down.size() && down.top().second < j) down.pop();
while (su.size() && su.top().second < j) su.pop();
if (ys[i + 1] - ys[j] >= W) mn = min(mn, max(up.top().first + down.top().first, su.top().first));
}
if (mn >= INF) return false;
ans = min(ans, mn + d - 1);
return true;
}
ll ans2 = INF;
void nc(ll l, ll r) {
vector<ll> ys;
ll i, j;
for (i = 1; i <= N; i++) ys.push_back(arr[i].second - l), ys.push_back(arr[i].second + r + 1);
ys.push_back(1);
ys.push_back(W + 1);
ys.push_back(W);
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
ll X = ys.size();
multiset<ll> ds, alls;
for (i = 0; i < X; i++) U[i] = D[i] = UD[i] = 0, st[i].clear(), en[i].clear();
for (i = 1; i <= N; i++) {
ll low, high;
low = lower_bound(ys.begin(), ys.end(), arr[i].second - l) - ys.begin();
high = lower_bound(ys.begin(), ys.end(), arr[i].second + r + 1) - ys.begin();
st[low].push_back(i);
en[high].push_back(i);
}
ll uu, dd, uudd;
uu = dd = uudd = 0;
for (i = 0; i < X; i++) {
for (auto v : st[i]) {
ll x = arr[v].first;
if (alls.size() && alls.find(x) == alls.end()) {
auto it = alls.lower_bound(x);
if (it == alls.end()) ds.insert(x - *(--it) - 1);
else if (it == alls.begin()) ds.insert(*it - x - 1);
else {
ll ne = *it;
it--;
ll pv = *it;
ds.erase(ds.find(ne - pv - 1));
ds.insert(ne - x - 1);
ds.insert(x - pv - 1);
}
}
alls.insert(x);
}
for (auto v : en[i]) {
ll x = arr[v].first;
alls.erase(alls.find(x));
if (alls.size() && alls.find(x) == alls.end()) {
auto it = alls.lower_bound(x);
if (it == alls.end()) ds.erase(ds.find(x - *(--it) - 1));
else if (it == alls.begin()) ds.erase(ds.find(*it - x - 1));
else {
ll ne = *it;
it--;
ll pv = *it;
ds.insert(ne - pv - 1);
ds.erase(ds.find(ne - x - 1));
ds.erase(ds.find(x - pv - 1));
}
}
}
if (ys[i] > 0 && ys[i] <= W) {
if (ds.size()) uudd = max(uudd, *ds.rbegin());
if (alls.empty()) uudd = INF;
else {
uu = max(uu, *alls.begin() - 1);
dd = max(dd, H - *alls.rbegin());
}
}
}
if (uudd < INF) ans2 = min(ans2, max(uu + dd, uudd) + l + r);
}
ll naive() {
vector<ll> lv;
ll i, j;
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) lv.push_back(abs(arr[j].second - arr[i].second));
lv.push_back(arr[i].second - 1);
lv.push_back(W - arr[i].second);
}
sort(lv.begin(), lv.end());
lv.erase(unique(lv.begin(), lv.end()), lv.end());
for (auto l : lv) for (auto r : lv) nc(l, r);
return ans2;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> H >> W >> N;
swap(H, W);
ll i, j;
vector<ll> ls;
ls.push_back(W);
for (i = 1; i <= N; i++) cin >> arr[i].first >> arr[i].second, swap(arr[i].first, arr[i].second);
vector<ll> sv;
for (i = 1; i <= N; i++) {
for (j = i + 1; j <= N; j++) ls.push_back(abs(arr[j].second - arr[i].second));
for (j = i + 1; j <= N; j++) ls.push_back(abs(arr[j].second - arr[i].second) + W);
ls.push_back(arr[i].second);
ls.push_back(W - arr[i].second + 1);
}
sort(ls.begin(), ls.end());
ls.erase(unique(ls.begin(), ls.end()), ls.end());
reverse(ls.begin(), ls.end());
while (ls.back() <= 0) ls.pop_back();
for (auto v : ls) test(v + i);
//assert(ans == naive());
cout << ans << ln;
}
Compilation message
cultivation.cpp: In function 'void nc(ll, ll)':
cultivation.cpp:102:8: warning: unused variable 'j' [-Wunused-variable]
102 | ll i, j;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
9796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
