# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
940797 |
2024-03-07T16:04:16 Z |
Pannda |
Aliens (IOI16_aliens) |
C++17 |
|
3 ms |
348 KB |
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
template <class T>
struct LiChao {
const T INF = numeric_limits<T>::max() / 2;
int C;
vector<T> dom;
vector<array<T, 2>> first;
vector<int> label;
T f(array<T, 2> p, int x) {
return p[0] * dom[x] + p[1];
}
LiChao(vector<T> _dom) : dom(_dom) {
sort(dom.begin(), dom.end());
dom.resize(unique(dom.begin(), dom.end()) - dom.begin());
C = dom.size();
first.resize(4 * C, array<T, 2>{0, INF});
label.resize(4 * C, -1);
}
void add(T a, T b, int lab) {
array<T, 2> p{a, b};
int idx = 0, l = 0, r = C;
while (l < r) {
int m = (l + r) >> 1;
bool doml = f(p, l) < f(first[idx], l);
bool domm = f(p, m) < f(first[idx], m);
if (domm) swap(p, first[idx]), swap(label[idx], lab);
if (l + 1 == r) break;
if (doml != domm) idx = 2 * idx + 1, r = m;
else idx = 2 * idx + 2, l = m;
}
}
pair<T, int> getMin(T x) {
// x -= 1e-9;
x = lower_bound(dom.begin(), dom.end(), x) - dom.begin();
T mn = INF;
int lab = -1;
int idx = 0, l = 0, r = C;
while (l < r) {
if (f(first[idx], x) < mn) mn = f(first[idx], x), lab = label[idx];
if (l + 1 == r) break;
int m = (l + r) >> 1;
if (x < m) idx = 2 * idx + 1, r = m;
else idx = 2 * idx + 2, l = m;
}
return make_pair(mn, lab);
}
};
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
auto [fl, fr] = [&]() -> array<vector<long long>, 2> {
vector<array<int, 2>> fetch;
for (int i = 0; i < n; i++) {
fetch.push_back({min(r[i], c[i]), max(r[i], c[i]) + 1});
}
sort(fetch.begin(), fetch.end(), [&](array<int, 2> lr0, array<int, 2> lr1) {
if (lr0[0] != lr1[0]) return lr0[0] < lr1[0];
return lr0[1] > lr1[1];
});
vector<long long> fl, fr;
for (auto [l, r] : fetch) {
if (!fr.empty() && r <= fr.back()) continue;
fl.push_back(l);
fr.push_back(r);
}
return {fl, fr};
}();
n = fl.size();
k = min(k, n);
auto getExtremum = [&](long long lambda) -> pair<long long, int> {
vector<long long> dp(n + 1);
vector<int> arg(n + 1);
dp[0] = arg[0] = 0;
LiChao<long long> lc(fr);
for (int i = 0; i < n; i++) {
long long d = max(0LL, i == 0 ? 0 : fr[i - 1] - fl[i]);
lc.add(-2 * fl[i], dp[i] + fl[i] * fl[i] - d * d, i);
auto [mn, j] = lc.getMin(fr[i]);
dp[i + 1] = mn + fr[i] * fr[i] + lambda;
arg[i + 1] = arg[j] + 1;
}
return make_pair(dp[n], arg[n]);
};
long long lambda = [&]() -> long long {
long long l = 0, r = 1e18;
while (l < r) {
long long m = (l + r) >> 1;
auto [extre, arg] = getExtremum(m);
if (arg <= k) {
r = m;
} else {
l = m + 1;
}
}
return l;
}();
auto [extre, arg] = getExtremum(lambda);
// cout << lambda << ' ' << extre << ' ' << arg << '\n';
return extre - lambda * arg;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 5 |
5 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 41 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 71923 |
7 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
8 |
Incorrect |
3 ms |
348 KB |
Wrong answer: output = 949, expected = 764 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 5 |
25 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 41 |
26 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
3 ms |
348 KB |
Wrong answer: output = 949, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 5 |
25 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 41 |
26 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
3 ms |
348 KB |
Wrong answer: output = 949, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 5 |
25 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 41 |
26 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
3 ms |
348 KB |
Wrong answer: output = 949, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 9502 |
12 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 5 |
25 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 41 |
26 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
3 ms |
348 KB |
Wrong answer: output = 949, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |