| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 361721 | saleh | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "aliens.h"
#include <bits/stdc++.h>
#define int long long
#define sz(x) ((int)x.size())
#define mp make_pair
using namespace std;
const int INF = LLONG_MAX, MAXN = 100 * 1000 + 2;
struct line {
mutable long double a, z;
mutable long double f;
mutable int ind;
bool operator < (const line& x) const { return a < x.a; }
bool operator < (int x) const { return f < x; }
};
long double ot(line x, line y) { return 1. * (y.z - x.z) / (x.a - y.a); }
struct lc : multiset<line, less<>> {
bool tabe (iterator x, iterator y) {
if (y == end()) return x -> f = INF, false;
if (x -> a == y -> a) x -> f = ((x -> z > y -> z)? INF : -INF);
else x -> f = ot(*x, *y);
return x -> f >= y -> f;
}
void add(long double x, long double y, int ind) {
auto nxt = insert({x, y, INF, ind}), h = nxt++, t = h;
while (tabe(h, nxt)) nxt = erase(nxt);
if (t != begin() && tabe(--t, h)) tabe(t, h = erase(h));
while ((h = t) != begin() && (--t) -> f >= h -> f) tabe(t, erase(h));
}
void operator += (lc x) {
if (x.size() > size()) swap(x);
for (auto i : x) add(i.a, i.z, i.ind);
x.clear();
}
pair<int, int> get(int x) {
auto l = lower_bound(x);
return {l -> a * x + l -> z, l -> ind};
}
};
int chi[MAXN];
long double dp[MAXN];
long long take_photos(int n, int m, int k, vector<int> l, vector<int> r) {
long long ans = m * m;
auto f = [&](long double x) -> int {
lc s;
dp[0] = (r[0] - l[0] + 1) * (r[0] - l[0] + 1);
s.add(2 * l[0], -(dp[0] + l[0] * l[0] + 2 * l[0] + 1), 0);
for (int i = 1; i < n; i++) {
auto cho = s.get(r[i]);
dp[i] = cho.first + r[i] * r[i] + 2 * r[i] + x;
chi[i] = chi[cho.second] + 1;
s.add(2 * l[i], -(dp[i] + l[i] * l[i] + 2 * l[i] + 1), i);
}
return chi[n - 1];
};
for (int i = 0; i < n; i++) if (r[i] < l[i]) swap(r[i], l[i]);
vector<int> a(n);
iota(a.begin(), a.end(), 0);
sort(a.begin(), a.end(), [&](int x, int y) { return mp(l[x], r[x]) < mp(l[y], r[y]); });
long double dw = 0, up = m * m + 1;
for (int i = 0; i < 100; i++) {
long double mid = (dw + up) / 2;
if (f(mid) > k) up = mid;
else dw = mid;
}
f(dw);
cout << ans;
return 0;
}
/*
int32_t main() {
return 0;
}*/