| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1197519 | yellowtoad | Aliens (IOI16_aliens) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define f first
#define s second
#define int long long
using namespace std;
long long n, m, k, a[1000010], sum, minn, dp[100010], lst[100010], ps[100010], slope[100010], c[100010];
vector<long long> v;
deque<pair<long double,int>> hull;
long double x_int(int i, int j) {
return (c[j]-c[i]+0.0)/(slope[i]-slope[j]);
}
void add(int i) {
while (hull.size()) {
if (hull.size() >= 2) {
if (x_int(hull.back().s,i) <= hull[hull.size()-2].f) hull.pop_back();
else break;
} else {
if (x_int(hull.back().s,i) <= 0) hull.pop_back();
else break;
}
}
if (hull.size()) hull.back().f = x_int(hull.back().s,i);
hull.push_back({9e18,i});
}
int find(int x) {
while (hull.front().f <= x) hull.pop_front();
return hull.front().s;
}
int check(long long pen) {
hull.clear();
dp[0] = 0;
slope[0] = -2*a[v[1]];
c[0] = 2*a[v[1]]*v[1]-ps[1]+pen;
hull.push_back({9e18,0});
for (int i = 1; i < v.size(); i++) {
int id = find(v[i]);
lst[i] = id;
dp[i] = slope[id]*v[i]+c[id]+ps[i]-pen*i;
//cout << dp[i] << endl;
if (i != v.size()-1) {
slope[i] = -2*a[v[i+1]];
c[i] = 2*a[v[i+1]]*v[i+1]-ps[i+1]+dp[i]+pen*(i+1);
add(i);
}
}
int cur = v.size()-1, cnt = 0;
while (cur) {
cnt += cur-lst[cur]-1;
cur = lst[cur];
}
//cout << cnt << endl;
return cnt;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
for (int i = 0; i < m; i++) a[i] = 1e18;
for (int i = 1; i <= n; i++) {
long long x, y;
cin >> x >> y;
if (x > y) swap(x,y);
a[y] = min(a[y],x);
}
minn = m;
for (int i = m-1; i >= 0; i--) {
if (a[i] < minn) {
sum += (i-a[i]+1)*(i-a[i]+1);
if (i >= minn) sum -= (i-minn+1)*(i-minn+1);
v.push_back(i);
minn = a[i];
}
}
if (v.size() <= k) {
cout << sum << endl;
return 0;
}
k = v.size()-k;
v.push_back(0);
reverse(v.begin(),v.end());
for (int i = 2; i < v.size(); i++) {
if (v[i-1] < a[v[i]]) ps[i] = ps[i-1]+a[v[i]]*(v[i]-a[v[i]]+1)*2+(v[i-1]+a[v[i]]+1)*(a[v[i]]-1-v[i-1]);
else ps[i] = ps[i-1]+a[v[i]]*(v[i]-v[i-1])*2;
}
long long l = 0, r = 1e12;
while (l <= r) {
long long mid = (l+r)/2;
//cout << "start: " << mid << endl;
if (check(mid) < k) l = mid+1;
else r = mid-1;
}
int tmp = check(l);
cout << dp[v.size()-1]+l*tmp+sum << endl;
}