| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1124767 | adaawf | Aliens (IOI16_aliens) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int, int>> vv, v;
pair<int, int> f[100005];
int mm;
struct LINE {
int a, b, num;
} t[4000005];
int trya(LINE a, int x) {
return a.a * x + a.b;
}
void update(int v, int tl, int tr, LINE x) {
int mid = (tl + tr) / 2;
int h = trya(t[v], mid), k = trya(x, mid);
if (h > k) swap(t[v], x);
if (h == k && x.num < t[v].num) swap(t[v], x);
if (tl == tr) return;
if (x.a < t[v].a) update(v * 2 + 1, mid + 1, tr, x);
else update(v * 2, tl, mid, x);
}
LINE sum(int v, int tl, int tr, int x) {
if (tl == tr) {
return t[v];
}
int mid = (tl + tr) / 2;
LINE g, l = t[v];
if (x <= mid) g = sum(v * 2, tl, mid, x);
else g = sum(v * 2 + 1, mid + 1, tr, x);
int h = trya(g, x), k = trya(l, x);
if (h > k) swap(g, l);
if (h == k && g.num < l.num) swap(g, l);
return g;
}
pair<int, int> check(int x) {
for (int i = 0; i <= mm * 4 + 1; i++) {
t[i] = {0, 1000000000000000000, 0};
}
for (int i = 1; i < v.size(); i++) {
int h = (v[i].first - 1) * (v[i].first - 1) + f[i - 1].first - max(v[i - 1].second - v[i].first + 1, 0ll) * max(v[i - 1].second - v[i].first + 1, 0ll);
update(1, 1, mm, {-2 * (v[i].first - 1), h, f[i - 1].second});
LINE k = sum(1, 1, mm, v[i].second);
f[i].first = trya(k, v[i].second) + v[i].second * v[i].second + x;
f[i].second = k.num + 1;
}
return f[v.size() - 1];
}
int take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
mm = m;
for (int i = 0; i < n; i++) {
vv.push_back({min(r[i], c[i]) + 1, max(r[i], c[i]) + 1});
}
sort(vv.begin(), vv.end());
v.push_back({-1, -1});
int ma = -1;
for (auto w : vv) {
if (w.second <= ma) continue;
if (!v.empty() && w.first == v.back().first) v.pop_back();
v.push_back(w);
ma = w.second;
}
int l = 0, rr = 1e12, res;
while (l <= rr) {
int mid = (l + rr) / 2;
if (check(mid).second <= k) {
res = mid;
rr = mid - 1;
}
else l = mid + 1;
}
pair<int, int> h = check(res);
return h.first - 1ll * k * res;
}