# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
751539 |
2023-05-31T17:21:37 Z |
Desh03 |
Aliens (IOI16_aliens) |
C++17 |
|
1 ms |
272 KB |
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
struct point {
int x, y;
bool operator < (const point &p) const {
return x == p.x ? y < p.y : x < p.x;
}
};
struct line {
int m;
long long c;
int s;
long long eval(const int &x) {
return 1LL * m * x + c;
}
bool good(const line &l1, const line &l2) {
return __int128(l1.c - l2.c) * (l1.m - m) < __int128(c - l1.c) * (l2.m - l1.m);
}
};
int N;
vector<point> r;
struct CHT {
deque<line> hull;
void insert(line l) {
while (hull.size() > 1 && !l.good(hull.back(), *next(hull.rbegin()))) hull.pop_back();
hull.push_back(l);
}
pair<long long, int> qry(int x) {
while (hull.size() > 1 && hull[0].eval(x) > hull[1].eval(x)) hull.pop_front();
return {hull[0].eval(x), hull[0].s};
}
};
long long sq(int x) {
return 1LL * x * x;
}
pair<long long, int> aliens(long long lambda) {
CHT cht;
cht.insert({-2 * r[0].x, sq(r[0].x) - 2 * r[0].x, 1});
for (int i = 0; i < N; i++) {
auto dp = cht.qry(r[i].y);
dp.first += sq(r[i].y + 1) + lambda;
if (i == N - 1) return dp;
cht.insert({-2 * r[i + 1].x, dp.first + sq(r[i + 1].x) - 2 * r[i + 1].x - sq(max(0, r[i].y - r[i + 1].x + 1)), dp.second + 1});
}
}
long long take_photos(int n, int m, int k, vector<int> R, vector<int> C) {
vector<point> f;
for (int i = 0; i < n; i++) {
if (R[i] > C[i]) swap(R[i], C[i]);
f.push_back({R[i], C[i]});
}
sort(f.begin(), f.end());
r.push_back(f[0]);
for (int i = 1; i < n; i++) {
if (r.back().x == f[i].x) {
r.pop_back();
r.push_back(f[i]);
} else if (f[i].y > r.back().y) {
r.push_back(f[i]);
}
}
N = r.size(), k = min(N, k);
long long l_ = 0, r_ = 1e11;
while (l_ < r_) {
long long m_ = l_ + r_ >> 1;
if (aliens(m_).second > k) l_ = m_ + 1;
else r_ = m_ ;
}
auto [x, y] = aliens(l_);
return x - l_ * y;
}
Compilation message
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:73:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
73 | long long m_ = l_ + r_ >> 1;
| ~~~^~~~
aliens.cpp: In function 'std::pair<long long int, int> aliens(long long int)':
aliens.cpp:44:8: warning: control reaches end of non-void function [-Wreturn-type]
44 | CHT cht;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 1 |
2 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
272 KB |
Correct answer: answer = 1 |
4 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 5 |
5 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 41 |
6 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 71923 |
7 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 77137 |
8 |
Incorrect |
1 ms |
212 KB |
Wrong answer: output = 925, expected = 764 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 1 |
22 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
272 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 5 |
25 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 41 |
26 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
1 ms |
212 KB |
Wrong answer: output = 925, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 1 |
22 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
272 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 5 |
25 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 41 |
26 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
1 ms |
212 KB |
Wrong answer: output = 925, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 1 |
22 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
272 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 5 |
25 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 41 |
26 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
1 ms |
212 KB |
Wrong answer: output = 925, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 1 |
22 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
272 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 5 |
25 |
Correct |
0 ms |
212 KB |
Correct answer: answer = 41 |
26 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
212 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
1 ms |
212 KB |
Wrong answer: output = 925, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |