# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
377977 |
2021-03-15T16:42:57 Z |
2qbingxuan |
Cake 3 (JOI19_cake3) |
C++14 |
|
644 ms |
9832 KB |
#include <bits/stdc++.h>
#ifdef local
#define debug(a...) qqbx(#a, a)
template <typename ...T> void qqbx(const char *s, T ...a) {
int cnt = sizeof...(T);
((std::cerr << "\033[1;32m(" << s << ") = (") , ... , (std::cerr << a << (--cnt ? ", " : "\033[0m)\n")));
}
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#else
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define pb emplace_back
#define sort_uni(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;
using ll = int64_t;
template <typename T> using min_heap = priority_queue<T, vector<T>, greater<T>>;
const ll INF = 1e18;
const int maxn = 500025, inf = 1e9;
struct Event {
int l, r, fl, fr;
};
vector<int> u;
struct kthMaxsum {
int cnt[maxn];
ll sum[maxn];
int sz;
void insert(int x) {
++sz;
int d = u[x];
for (++x; x < maxn; x += x & -x)
cnt[x] += 1, sum[x] += d;
}
void erase(int x) {
--sz;
int d = u[x];
for (++x; x < maxn; x += x & -x)
cnt[x] -= 1, sum[x] -= d;
}
ll query(int k) {
if (sz < k) return -INF;
int p = 0;
for (int s = 1 << 20; s; s >>= 1) {
if (p + s < maxn && cnt[p + s] < k) {
k -= cnt[p += s];
}
}
ll res = 1LL * u[p] * k;
for (; p > 0; p -= p & -p)
res += sum[p];
return res;
}
} ds;
pair<int,int> v[maxn];
int n, k;
int id[maxn];
void update(int l, int r) { // [l, r]
static int curL = 1, curR = 0;
while (curR < r) ds.insert(id[++curR]);
while (curL > l) ds.insert(id[--curL]);
while (curR > r) ds.erase(id[curR--]);
while (curL < l) ds.erase(id[curL++]);
}
ll res = -INF;
void solve(int l, int r, int fl, int fr) {
if (l == r) return;
int m = (l+r)/2;
ll ans = -INF;
int pos = -1;
for (int i = fl; i < fr && i < m; i++) {
update(i+1, m-1);
ll cur = ds.query(k) + v[i].second + v[m].second - abs(v[i].first - v[m].first) * 2;
if (ans < cur) {
ans = cur;
pos = i;
}
}
res = max(res, ans);
solve(l, m, fl, pos+1);
solve(m+1, r, pos, fr);
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> k;
/*
int seed = time(0);
debug(seed);
srand(seed);
for (int i = 0; i < n; i++) v[i] = {rand() % 10, rand() % 10};
*/
for (int i = 0; i < n; i++) cin >> v[i].second >> v[i].first;
sort(v, v+n);
k -= 2;
/*
ll ans = -INF;
for (int i = 0; i < n; i++) {
priority_queue<int, vector<int>, greater<int>> pq;
ll sum = 0;
for (int j = i+1; j < n; j++) {
if (pq.size() == k)
ans = max(ans, sum + v[i].second + v[j].second - (v[j].first - v[i].first) * 2);
sum += v[j].second, pq.push(v[j].second);
if (pq.size() > k) sum -= pq.top(), pq.pop();
}
}
debug(ans);
*/
for (int i = 0; i < n; i++) u.push_back(v[i].second);
sort_uni(u);
reverse(all(u));
for (int i = 0; i < n; i++) id[i] = lower_bound(all(u), v[i].second, greater<>()) - u.begin();
solve(k+1, n, 0, n);
cout << res << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
492 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
492 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
500 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
1 ms |
492 KB |
Output is correct |
22 |
Correct |
1 ms |
492 KB |
Output is correct |
23 |
Correct |
1 ms |
512 KB |
Output is correct |
24 |
Correct |
1 ms |
492 KB |
Output is correct |
25 |
Correct |
1 ms |
492 KB |
Output is correct |
26 |
Correct |
1 ms |
492 KB |
Output is correct |
27 |
Correct |
1 ms |
492 KB |
Output is correct |
28 |
Correct |
1 ms |
492 KB |
Output is correct |
29 |
Correct |
1 ms |
492 KB |
Output is correct |
30 |
Correct |
1 ms |
492 KB |
Output is correct |
31 |
Correct |
1 ms |
492 KB |
Output is correct |
32 |
Correct |
1 ms |
492 KB |
Output is correct |
33 |
Correct |
1 ms |
492 KB |
Output is correct |
34 |
Correct |
1 ms |
492 KB |
Output is correct |
35 |
Correct |
1 ms |
492 KB |
Output is correct |
36 |
Correct |
1 ms |
492 KB |
Output is correct |
37 |
Correct |
2 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
492 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
492 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
500 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
1 ms |
492 KB |
Output is correct |
22 |
Correct |
1 ms |
492 KB |
Output is correct |
23 |
Correct |
1 ms |
512 KB |
Output is correct |
24 |
Correct |
1 ms |
492 KB |
Output is correct |
25 |
Correct |
1 ms |
492 KB |
Output is correct |
26 |
Correct |
1 ms |
492 KB |
Output is correct |
27 |
Correct |
1 ms |
492 KB |
Output is correct |
28 |
Correct |
1 ms |
492 KB |
Output is correct |
29 |
Correct |
1 ms |
492 KB |
Output is correct |
30 |
Correct |
1 ms |
492 KB |
Output is correct |
31 |
Correct |
1 ms |
492 KB |
Output is correct |
32 |
Correct |
1 ms |
492 KB |
Output is correct |
33 |
Correct |
1 ms |
492 KB |
Output is correct |
34 |
Correct |
1 ms |
492 KB |
Output is correct |
35 |
Correct |
1 ms |
492 KB |
Output is correct |
36 |
Correct |
1 ms |
492 KB |
Output is correct |
37 |
Correct |
2 ms |
492 KB |
Output is correct |
38 |
Correct |
4 ms |
492 KB |
Output is correct |
39 |
Correct |
4 ms |
492 KB |
Output is correct |
40 |
Correct |
4 ms |
492 KB |
Output is correct |
41 |
Correct |
4 ms |
492 KB |
Output is correct |
42 |
Correct |
5 ms |
492 KB |
Output is correct |
43 |
Correct |
3 ms |
492 KB |
Output is correct |
44 |
Correct |
6 ms |
620 KB |
Output is correct |
45 |
Correct |
4 ms |
492 KB |
Output is correct |
46 |
Correct |
5 ms |
492 KB |
Output is correct |
47 |
Correct |
5 ms |
492 KB |
Output is correct |
48 |
Correct |
4 ms |
512 KB |
Output is correct |
49 |
Correct |
4 ms |
492 KB |
Output is correct |
50 |
Correct |
4 ms |
492 KB |
Output is correct |
51 |
Correct |
4 ms |
492 KB |
Output is correct |
52 |
Correct |
4 ms |
640 KB |
Output is correct |
53 |
Correct |
4 ms |
492 KB |
Output is correct |
54 |
Correct |
4 ms |
492 KB |
Output is correct |
55 |
Correct |
3 ms |
492 KB |
Output is correct |
56 |
Correct |
3 ms |
492 KB |
Output is correct |
57 |
Correct |
4 ms |
492 KB |
Output is correct |
58 |
Correct |
4 ms |
492 KB |
Output is correct |
59 |
Correct |
4 ms |
492 KB |
Output is correct |
60 |
Correct |
6 ms |
620 KB |
Output is correct |
61 |
Correct |
4 ms |
492 KB |
Output is correct |
62 |
Correct |
4 ms |
492 KB |
Output is correct |
63 |
Correct |
4 ms |
492 KB |
Output is correct |
64 |
Correct |
4 ms |
492 KB |
Output is correct |
65 |
Correct |
4 ms |
492 KB |
Output is correct |
66 |
Correct |
4 ms |
492 KB |
Output is correct |
67 |
Correct |
4 ms |
492 KB |
Output is correct |
68 |
Correct |
4 ms |
492 KB |
Output is correct |
69 |
Correct |
4 ms |
580 KB |
Output is correct |
70 |
Correct |
4 ms |
492 KB |
Output is correct |
71 |
Correct |
4 ms |
492 KB |
Output is correct |
72 |
Correct |
4 ms |
492 KB |
Output is correct |
73 |
Correct |
4 ms |
492 KB |
Output is correct |
74 |
Correct |
2 ms |
492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
492 KB |
Output is correct |
2 |
Correct |
1 ms |
492 KB |
Output is correct |
3 |
Correct |
1 ms |
492 KB |
Output is correct |
4 |
Correct |
1 ms |
492 KB |
Output is correct |
5 |
Correct |
1 ms |
492 KB |
Output is correct |
6 |
Correct |
1 ms |
492 KB |
Output is correct |
7 |
Correct |
1 ms |
492 KB |
Output is correct |
8 |
Correct |
1 ms |
492 KB |
Output is correct |
9 |
Correct |
1 ms |
512 KB |
Output is correct |
10 |
Correct |
1 ms |
492 KB |
Output is correct |
11 |
Correct |
1 ms |
492 KB |
Output is correct |
12 |
Correct |
1 ms |
492 KB |
Output is correct |
13 |
Correct |
1 ms |
492 KB |
Output is correct |
14 |
Correct |
1 ms |
492 KB |
Output is correct |
15 |
Correct |
1 ms |
492 KB |
Output is correct |
16 |
Correct |
1 ms |
500 KB |
Output is correct |
17 |
Correct |
1 ms |
492 KB |
Output is correct |
18 |
Correct |
1 ms |
492 KB |
Output is correct |
19 |
Correct |
1 ms |
492 KB |
Output is correct |
20 |
Correct |
1 ms |
492 KB |
Output is correct |
21 |
Correct |
1 ms |
492 KB |
Output is correct |
22 |
Correct |
1 ms |
492 KB |
Output is correct |
23 |
Correct |
1 ms |
512 KB |
Output is correct |
24 |
Correct |
1 ms |
492 KB |
Output is correct |
25 |
Correct |
1 ms |
492 KB |
Output is correct |
26 |
Correct |
1 ms |
492 KB |
Output is correct |
27 |
Correct |
1 ms |
492 KB |
Output is correct |
28 |
Correct |
1 ms |
492 KB |
Output is correct |
29 |
Correct |
1 ms |
492 KB |
Output is correct |
30 |
Correct |
1 ms |
492 KB |
Output is correct |
31 |
Correct |
1 ms |
492 KB |
Output is correct |
32 |
Correct |
1 ms |
492 KB |
Output is correct |
33 |
Correct |
1 ms |
492 KB |
Output is correct |
34 |
Correct |
1 ms |
492 KB |
Output is correct |
35 |
Correct |
1 ms |
492 KB |
Output is correct |
36 |
Correct |
1 ms |
492 KB |
Output is correct |
37 |
Correct |
2 ms |
492 KB |
Output is correct |
38 |
Correct |
4 ms |
492 KB |
Output is correct |
39 |
Correct |
4 ms |
492 KB |
Output is correct |
40 |
Correct |
4 ms |
492 KB |
Output is correct |
41 |
Correct |
4 ms |
492 KB |
Output is correct |
42 |
Correct |
5 ms |
492 KB |
Output is correct |
43 |
Correct |
3 ms |
492 KB |
Output is correct |
44 |
Correct |
6 ms |
620 KB |
Output is correct |
45 |
Correct |
4 ms |
492 KB |
Output is correct |
46 |
Correct |
5 ms |
492 KB |
Output is correct |
47 |
Correct |
5 ms |
492 KB |
Output is correct |
48 |
Correct |
4 ms |
512 KB |
Output is correct |
49 |
Correct |
4 ms |
492 KB |
Output is correct |
50 |
Correct |
4 ms |
492 KB |
Output is correct |
51 |
Correct |
4 ms |
492 KB |
Output is correct |
52 |
Correct |
4 ms |
640 KB |
Output is correct |
53 |
Correct |
4 ms |
492 KB |
Output is correct |
54 |
Correct |
4 ms |
492 KB |
Output is correct |
55 |
Correct |
3 ms |
492 KB |
Output is correct |
56 |
Correct |
3 ms |
492 KB |
Output is correct |
57 |
Correct |
4 ms |
492 KB |
Output is correct |
58 |
Correct |
4 ms |
492 KB |
Output is correct |
59 |
Correct |
4 ms |
492 KB |
Output is correct |
60 |
Correct |
6 ms |
620 KB |
Output is correct |
61 |
Correct |
4 ms |
492 KB |
Output is correct |
62 |
Correct |
4 ms |
492 KB |
Output is correct |
63 |
Correct |
4 ms |
492 KB |
Output is correct |
64 |
Correct |
4 ms |
492 KB |
Output is correct |
65 |
Correct |
4 ms |
492 KB |
Output is correct |
66 |
Correct |
4 ms |
492 KB |
Output is correct |
67 |
Correct |
4 ms |
492 KB |
Output is correct |
68 |
Correct |
4 ms |
492 KB |
Output is correct |
69 |
Correct |
4 ms |
580 KB |
Output is correct |
70 |
Correct |
4 ms |
492 KB |
Output is correct |
71 |
Correct |
4 ms |
492 KB |
Output is correct |
72 |
Correct |
4 ms |
492 KB |
Output is correct |
73 |
Correct |
4 ms |
492 KB |
Output is correct |
74 |
Correct |
2 ms |
492 KB |
Output is correct |
75 |
Correct |
599 ms |
8936 KB |
Output is correct |
76 |
Correct |
617 ms |
9064 KB |
Output is correct |
77 |
Correct |
540 ms |
9320 KB |
Output is correct |
78 |
Correct |
644 ms |
9352 KB |
Output is correct |
79 |
Correct |
245 ms |
9448 KB |
Output is correct |
80 |
Correct |
353 ms |
9292 KB |
Output is correct |
81 |
Correct |
521 ms |
6632 KB |
Output is correct |
82 |
Correct |
594 ms |
7016 KB |
Output is correct |
83 |
Correct |
571 ms |
7016 KB |
Output is correct |
84 |
Correct |
569 ms |
7016 KB |
Output is correct |
85 |
Correct |
520 ms |
6888 KB |
Output is correct |
86 |
Correct |
409 ms |
6632 KB |
Output is correct |
87 |
Correct |
425 ms |
6376 KB |
Output is correct |
88 |
Correct |
529 ms |
6376 KB |
Output is correct |
89 |
Correct |
482 ms |
6632 KB |
Output is correct |
90 |
Correct |
445 ms |
6888 KB |
Output is correct |
91 |
Correct |
383 ms |
6364 KB |
Output is correct |
92 |
Correct |
403 ms |
6248 KB |
Output is correct |
93 |
Correct |
421 ms |
6504 KB |
Output is correct |
94 |
Correct |
382 ms |
6760 KB |
Output is correct |
95 |
Correct |
427 ms |
6888 KB |
Output is correct |
96 |
Correct |
589 ms |
6120 KB |
Output is correct |
97 |
Correct |
623 ms |
6760 KB |
Output is correct |
98 |
Correct |
631 ms |
6504 KB |
Output is correct |
99 |
Correct |
571 ms |
6504 KB |
Output is correct |
100 |
Correct |
543 ms |
6248 KB |
Output is correct |
101 |
Correct |
572 ms |
6220 KB |
Output is correct |
102 |
Correct |
498 ms |
6248 KB |
Output is correct |
103 |
Correct |
491 ms |
6168 KB |
Output is correct |
104 |
Correct |
511 ms |
6492 KB |
Output is correct |
105 |
Correct |
500 ms |
6492 KB |
Output is correct |
106 |
Correct |
575 ms |
6632 KB |
Output is correct |
107 |
Correct |
496 ms |
6504 KB |
Output is correct |
108 |
Correct |
563 ms |
9340 KB |
Output is correct |
109 |
Correct |
581 ms |
9704 KB |
Output is correct |
110 |
Correct |
466 ms |
5736 KB |
Output is correct |
111 |
Correct |
536 ms |
5736 KB |
Output is correct |
112 |
Correct |
325 ms |
7784 KB |
Output is correct |
113 |
Correct |
134 ms |
9832 KB |
Output is correct |