| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 521393 | pokmui9909 | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using lf = long double;
#define x first
#define y second
ll N, M, K;
pair<ll, ll> A[100005];
ll L[100005];
ll R[100005];
pair<ll, ll> D[100005];
void init(){
sort(A + 1, A + N + 1, [&](pair<ll, ll> a, pair<ll, ll> b) -> bool{
if(a.y != b.y) return a.y < b.y;
else return a.x > b.x;
});
vector<pair<ll, ll>> B;
for(int i = 1; i <= N; i++){
while(B.size() && B.back().x >= A[i].x) B.pop_back();
B.push_back(A[i]);
}
for(int i = 0; i < B.size(); i++){
L[i + 1] = B[i].x, R[i + 1] = B[i].y;
}
N = B.size();
}
struct Line{
ll a, b, i;
ll f(ll x){
return a * x + b;
}
};
lf X_cross(Line f, Line g){
return 1.0 * (f.b - g.b) / (g.a - f.a);
}
ll f(ll v){
deque<Line> dq;
dq.push_back({-4 * L[1], 2 * L[1] * L[1], 0});
for(int i = 1; i <= N; i++){
while(dq.size() >= 2 && dq[0].f(R[i] + 1) >= dq[1].f(R[i] + 1)) dq.pop_front();
D[i].x = dq[0].f(R[i] + 1) + (R[i] + 1) * (R[i] + 1) * 2 + v;
D[i].y = dq[0].i + 1;
Line f = {-4 * L[i + 1], D[i].x - max(0LL,R[i]-L[i+1]+1)*max(0LL,R[i]-L[i+1]+1)*2 + L[i+1]*L[i+1]*2, D[i].y};
while(dq.size() >= 2 && X_cross(f, dq[dq.size() - 2]) >= X_cross(f, dq[dq.size() - 1])) dq.pop_back();
dq.push_back(f);
}
return D[N].y;
}
int main(){
cin.tie(0) -> sync_with_stdio(false);
cin >> N >> M >> K;
for(int i = 1; i <= N; i++){
cin >> A[i].x >> A[i].y;
A[i].x++; A[i].y++;
if(A[i].x > A[i].y){
swap(A[i].x, A[i].y);
}
}
init();
ll S = 0, E = 1e12 + 7;
while(S <= E){
ll m = (S + E) / 2;
if(f(m * 2) <= K) E = m - 1;
else S = m + 1;
}
f(S * 2);
cout << (D[N].x - S * K) / 2;
}