| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 67084 |
2018-08-13T10:25:32 Z |
aome |
Candies (JOI18_candies) |
C++17 |
|
465 ms |
70060 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const long long INF = 1e18;
struct Seg {
int l, r;
long long w;
Seg (int l, int r, long long w) :
l(l), r(r), w(w) {}
bool operator < (const Seg& rhs) const {
return w < rhs.w;
}
};
int n;
int a[N];
long long res;
long long sum[2][N];
vector<Seg> vec;
set< pair<int, int> > s;
priority_queue<Seg> pq1, pq2;
int main() {
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
sum[0][i] = sum[0][i - 1] + a[i] * (i % 2 == 0);
sum[1][i] = sum[1][i - 1] + a[i] * (i % 2 == 1);
pq1.push(Seg(i, i, a[i]));
}
for (int i = 1; i <= (n + 1) / 2; ++i) {
long long v1 = -INF, v2 = -INF;
while (pq1.size()) {
long long w = pq1.top().w;
int p = pq1.top().l;
auto it = s.lower_bound(make_pair(p + 2, 0));
if (it != s.begin() && (--it) -> second + 1 >= p) pq1.pop();
else { v1 = w; break; }
}
while (pq2.size()) {
long long w = pq2.top().w;
int l = pq2.top().l, r = pq2.top().r;
if (s.find(make_pair(l, r)) == s.end()) pq2.pop();
else { v2 = w; break; }
}
int l, r;
res += max(v1, v2);
if (v1 >= v2) {
l = pq1.top().l, r = pq1.top().r, pq1.pop();
// cout << "#add " << l << '\n';
}
else {
l = pq2.top().l, r = pq2.top().r, pq2.pop();
s.erase(s.find(make_pair(l, r))), l--, r++;
// cout << "#modify " << l << ' ' << r << '\n';
}
auto it = s.lower_bound(make_pair(l, r));
if (it != s.end() && (it -> first) == r + 2) {
r = (it -> second), s.erase(it);
}
it = s.lower_bound(make_pair(l, r));
if (it != s.begin() && (--it) -> second == l - 2) {
l = (it -> first), s.erase(it);
}
bool t = l % 2;
if (l > 1 && r < n) {
pq2.push(Seg(l, r, (sum[t ^ 1][r + 1] - sum[t ^ 1][l - 2]) - (sum[t][r] - sum[t][l - 1])));
}
s.insert(make_pair(l, r));
// cout << "#\n";
// for (auto j : s) cout << j.first << ' ' << j.second << '\n';
cout << res << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
504 KB |
Output is correct |
| 2 |
Correct |
5 ms |
616 KB |
Output is correct |
| 3 |
Correct |
5 ms |
716 KB |
Output is correct |
| 4 |
Correct |
6 ms |
716 KB |
Output is correct |
| 5 |
Correct |
4 ms |
728 KB |
Output is correct |
| 6 |
Correct |
5 ms |
880 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1020 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1020 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1048 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1072 KB |
Output is correct |
| 11 |
Correct |
5 ms |
1072 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1132 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1180 KB |
Output is correct |
| 15 |
Correct |
4 ms |
1276 KB |
Output is correct |
| 16 |
Correct |
4 ms |
1316 KB |
Output is correct |
| 17 |
Correct |
7 ms |
1336 KB |
Output is correct |
| 18 |
Correct |
6 ms |
1484 KB |
Output is correct |
| 19 |
Correct |
5 ms |
1484 KB |
Output is correct |
| 20 |
Correct |
4 ms |
1484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
504 KB |
Output is correct |
| 2 |
Correct |
5 ms |
616 KB |
Output is correct |
| 3 |
Correct |
5 ms |
716 KB |
Output is correct |
| 4 |
Correct |
6 ms |
716 KB |
Output is correct |
| 5 |
Correct |
4 ms |
728 KB |
Output is correct |
| 6 |
Correct |
5 ms |
880 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1020 KB |
Output is correct |
| 8 |
Correct |
5 ms |
1020 KB |
Output is correct |
| 9 |
Correct |
4 ms |
1048 KB |
Output is correct |
| 10 |
Correct |
3 ms |
1072 KB |
Output is correct |
| 11 |
Correct |
5 ms |
1072 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1132 KB |
Output is correct |
| 13 |
Correct |
6 ms |
1132 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1180 KB |
Output is correct |
| 15 |
Correct |
4 ms |
1276 KB |
Output is correct |
| 16 |
Correct |
4 ms |
1316 KB |
Output is correct |
| 17 |
Correct |
7 ms |
1336 KB |
Output is correct |
| 18 |
Correct |
6 ms |
1484 KB |
Output is correct |
| 19 |
Correct |
5 ms |
1484 KB |
Output is correct |
| 20 |
Correct |
4 ms |
1484 KB |
Output is correct |
| 21 |
Correct |
455 ms |
15516 KB |
Output is correct |
| 22 |
Correct |
460 ms |
17452 KB |
Output is correct |
| 23 |
Correct |
439 ms |
19340 KB |
Output is correct |
| 24 |
Correct |
249 ms |
21164 KB |
Output is correct |
| 25 |
Correct |
226 ms |
22912 KB |
Output is correct |
| 26 |
Correct |
228 ms |
24728 KB |
Output is correct |
| 27 |
Correct |
242 ms |
26732 KB |
Output is correct |
| 28 |
Correct |
253 ms |
28600 KB |
Output is correct |
| 29 |
Correct |
258 ms |
30688 KB |
Output is correct |
| 30 |
Correct |
288 ms |
32720 KB |
Output is correct |
| 31 |
Correct |
309 ms |
34752 KB |
Output is correct |
| 32 |
Correct |
282 ms |
36652 KB |
Output is correct |
| 33 |
Correct |
315 ms |
38484 KB |
Output is correct |
| 34 |
Correct |
313 ms |
40200 KB |
Output is correct |
| 35 |
Correct |
318 ms |
41988 KB |
Output is correct |
| 36 |
Correct |
360 ms |
43568 KB |
Output is correct |
| 37 |
Correct |
358 ms |
45568 KB |
Output is correct |
| 38 |
Correct |
465 ms |
47632 KB |
Output is correct |
| 39 |
Correct |
236 ms |
49320 KB |
Output is correct |
| 40 |
Correct |
259 ms |
51116 KB |
Output is correct |
| 41 |
Correct |
265 ms |
53004 KB |
Output is correct |
| 42 |
Correct |
258 ms |
54804 KB |
Output is correct |
| 43 |
Correct |
242 ms |
56776 KB |
Output is correct |
| 44 |
Correct |
253 ms |
58744 KB |
Output is correct |
| 45 |
Correct |
241 ms |
60876 KB |
Output is correct |
| 46 |
Correct |
262 ms |
62964 KB |
Output is correct |
| 47 |
Correct |
259 ms |
64728 KB |
Output is correct |
| 48 |
Correct |
318 ms |
66588 KB |
Output is correct |
| 49 |
Correct |
394 ms |
68308 KB |
Output is correct |
| 50 |
Correct |
346 ms |
70060 KB |
Output is correct |
