# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
330966 |
2020-11-27T01:56:32 Z |
12tqian |
Cake 3 (JOI19_cake3) |
C++17 |
|
1149 ms |
150636 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 5e6;
const int N = 2e5 + 5;
struct Node {
int lc;
int rc;
ll sum = 0;
int num = 0;
} t[M];
int cnt = 0;
int ti[N];
ll v[N];
ll c[N];
ll ans[N];
ll ord[N];
int n, m;
int modify(int p, int l, int r, int x, int v) {
int u = ++cnt;
if (l == r) {
t[u].sum = t[p].sum + v;
t[u].num = t[p].num + 1;
} else {
int m = (l + r) / 2;
if (x <= m) {
t[u].lc = modify(t[p].lc, l, m, x, v);
t[u].rc = t[p].rc;
} else {
t[u].lc = t[p].lc;
t[u].rc = modify(t[p].rc, m + 1, r, x, v);
}
t[u].sum = t[t[u].lc].sum + t[t[u].rc].sum;
t[u].num = t[t[u].lc].num + t[t[u].rc].num;
}
return u;
}
// make sure it's stuff for l - 1, r
ll query(int num, int pl, int pr, int l, int r) {
// need the highest num in the range [l, r]
if (num == 0)
return 0;
if (l == r) {
return 1LL * ord[l] * num;
}
int mid = (l + r) / 2;
ll rsum = t[t[pr].rc].sum - t[t[pl].rc].sum;
int rnum = t[t[pr].rc].num - t[t[pl].rc].num;
if (rnum >= num)
return query(num, t[pl].rc, t[pr].rc, mid + 1, r);
else
return rsum + query(num - rnum, t[pl].lc, t[pr].lc, l, mid);
}
ll evaluate(int num, int l, int r) {
ll res = query(num , ti[l - 1], ti[r], 1, n);
return res;
}
ll f(int l, int r) {
return evaluate(m, l, r) - 2 * (c[r] - c[l]);
}
void dnc(int l, int r, int gl, int gr) {
if (l > r) return;
int mid = (l + r) / 2;
int best = gl;
for (int i = max(mid + m - 1, gl); i <= gr; i++) {
ll cur = f(mid, i);
assert(i - mid + 1 >= m);
if (cur > ans[mid])
ans[mid] = cur, best = i;
}
dnc(l, mid - 1, gl, best);
dnc(mid + 1, r, best, gr);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; i++)
ans[i] = -2e18;
vector<array<ll, 2>> parts(n);
for (int i = 0; i < n; i++)
cin >> parts[i][0] >> parts[i][1];
sort(parts.begin(), parts.end(), [](array<ll, 2> a, array<ll, 2> b) {
return a[1] < b[1];
});
for (int i = 1; i <= n; i++) {
v[i] = parts[i - 1][0];
c[i] = parts[i - 1][1];
}
set<int> vals;
for (int i = 1; i <= n; i++)
vals.insert(v[i]);
map<int, int> conv;
int num = 1;
for (int x : vals)
conv[x] = num, ord[num] = x, num++;
for (int i = 1; i <= n; i++) {
ti[i] = modify(ti[i - 1], 1, n, conv[v[i]], v[i]);
}
dnc(1, n - m + 1, 1, n);
ll res = -2e18 ;
for (int i = 1; i <= n; i++)
res = max(res, ans[i]);
cout << res << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
117740 KB |
Output is correct |
2 |
Correct |
63 ms |
117740 KB |
Output is correct |
3 |
Correct |
63 ms |
117740 KB |
Output is correct |
4 |
Correct |
62 ms |
117840 KB |
Output is correct |
5 |
Correct |
64 ms |
117868 KB |
Output is correct |
6 |
Correct |
65 ms |
117740 KB |
Output is correct |
7 |
Correct |
63 ms |
117740 KB |
Output is correct |
8 |
Correct |
64 ms |
117740 KB |
Output is correct |
9 |
Correct |
63 ms |
117740 KB |
Output is correct |
10 |
Correct |
71 ms |
117740 KB |
Output is correct |
11 |
Correct |
72 ms |
117868 KB |
Output is correct |
12 |
Correct |
74 ms |
117740 KB |
Output is correct |
13 |
Correct |
64 ms |
117740 KB |
Output is correct |
14 |
Correct |
64 ms |
117740 KB |
Output is correct |
15 |
Correct |
64 ms |
117868 KB |
Output is correct |
16 |
Correct |
74 ms |
117784 KB |
Output is correct |
17 |
Correct |
66 ms |
117740 KB |
Output is correct |
18 |
Correct |
64 ms |
117740 KB |
Output is correct |
19 |
Correct |
64 ms |
117740 KB |
Output is correct |
20 |
Correct |
66 ms |
117740 KB |
Output is correct |
21 |
Correct |
64 ms |
117740 KB |
Output is correct |
22 |
Correct |
67 ms |
117740 KB |
Output is correct |
23 |
Correct |
64 ms |
117740 KB |
Output is correct |
24 |
Correct |
63 ms |
117740 KB |
Output is correct |
25 |
Correct |
64 ms |
117740 KB |
Output is correct |
26 |
Correct |
66 ms |
117740 KB |
Output is correct |
27 |
Correct |
64 ms |
117740 KB |
Output is correct |
28 |
Correct |
63 ms |
117740 KB |
Output is correct |
29 |
Correct |
70 ms |
117996 KB |
Output is correct |
30 |
Correct |
70 ms |
117740 KB |
Output is correct |
31 |
Correct |
67 ms |
117868 KB |
Output is correct |
32 |
Correct |
64 ms |
117740 KB |
Output is correct |
33 |
Correct |
64 ms |
117740 KB |
Output is correct |
34 |
Correct |
64 ms |
117952 KB |
Output is correct |
35 |
Correct |
65 ms |
117740 KB |
Output is correct |
36 |
Correct |
64 ms |
117740 KB |
Output is correct |
37 |
Correct |
64 ms |
117740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
117740 KB |
Output is correct |
2 |
Correct |
63 ms |
117740 KB |
Output is correct |
3 |
Correct |
63 ms |
117740 KB |
Output is correct |
4 |
Correct |
62 ms |
117840 KB |
Output is correct |
5 |
Correct |
64 ms |
117868 KB |
Output is correct |
6 |
Correct |
65 ms |
117740 KB |
Output is correct |
7 |
Correct |
63 ms |
117740 KB |
Output is correct |
8 |
Correct |
64 ms |
117740 KB |
Output is correct |
9 |
Correct |
63 ms |
117740 KB |
Output is correct |
10 |
Correct |
71 ms |
117740 KB |
Output is correct |
11 |
Correct |
72 ms |
117868 KB |
Output is correct |
12 |
Correct |
74 ms |
117740 KB |
Output is correct |
13 |
Correct |
64 ms |
117740 KB |
Output is correct |
14 |
Correct |
64 ms |
117740 KB |
Output is correct |
15 |
Correct |
64 ms |
117868 KB |
Output is correct |
16 |
Correct |
74 ms |
117784 KB |
Output is correct |
17 |
Correct |
66 ms |
117740 KB |
Output is correct |
18 |
Correct |
64 ms |
117740 KB |
Output is correct |
19 |
Correct |
64 ms |
117740 KB |
Output is correct |
20 |
Correct |
66 ms |
117740 KB |
Output is correct |
21 |
Correct |
64 ms |
117740 KB |
Output is correct |
22 |
Correct |
67 ms |
117740 KB |
Output is correct |
23 |
Correct |
64 ms |
117740 KB |
Output is correct |
24 |
Correct |
63 ms |
117740 KB |
Output is correct |
25 |
Correct |
64 ms |
117740 KB |
Output is correct |
26 |
Correct |
66 ms |
117740 KB |
Output is correct |
27 |
Correct |
64 ms |
117740 KB |
Output is correct |
28 |
Correct |
63 ms |
117740 KB |
Output is correct |
29 |
Correct |
70 ms |
117996 KB |
Output is correct |
30 |
Correct |
70 ms |
117740 KB |
Output is correct |
31 |
Correct |
67 ms |
117868 KB |
Output is correct |
32 |
Correct |
64 ms |
117740 KB |
Output is correct |
33 |
Correct |
64 ms |
117740 KB |
Output is correct |
34 |
Correct |
64 ms |
117952 KB |
Output is correct |
35 |
Correct |
65 ms |
117740 KB |
Output is correct |
36 |
Correct |
64 ms |
117740 KB |
Output is correct |
37 |
Correct |
64 ms |
117740 KB |
Output is correct |
38 |
Correct |
66 ms |
118124 KB |
Output is correct |
39 |
Correct |
64 ms |
118124 KB |
Output is correct |
40 |
Correct |
75 ms |
118124 KB |
Output is correct |
41 |
Correct |
67 ms |
118124 KB |
Output is correct |
42 |
Correct |
64 ms |
118124 KB |
Output is correct |
43 |
Correct |
64 ms |
118124 KB |
Output is correct |
44 |
Correct |
72 ms |
118124 KB |
Output is correct |
45 |
Correct |
66 ms |
118124 KB |
Output is correct |
46 |
Correct |
67 ms |
118124 KB |
Output is correct |
47 |
Correct |
67 ms |
118252 KB |
Output is correct |
48 |
Correct |
66 ms |
118124 KB |
Output is correct |
49 |
Correct |
65 ms |
118124 KB |
Output is correct |
50 |
Correct |
66 ms |
118124 KB |
Output is correct |
51 |
Correct |
65 ms |
118124 KB |
Output is correct |
52 |
Correct |
65 ms |
118124 KB |
Output is correct |
53 |
Correct |
67 ms |
118124 KB |
Output is correct |
54 |
Correct |
73 ms |
118124 KB |
Output is correct |
55 |
Correct |
66 ms |
118124 KB |
Output is correct |
56 |
Correct |
66 ms |
118124 KB |
Output is correct |
57 |
Correct |
65 ms |
118124 KB |
Output is correct |
58 |
Correct |
67 ms |
118124 KB |
Output is correct |
59 |
Correct |
67 ms |
117868 KB |
Output is correct |
60 |
Correct |
65 ms |
117868 KB |
Output is correct |
61 |
Correct |
64 ms |
117996 KB |
Output is correct |
62 |
Correct |
63 ms |
117868 KB |
Output is correct |
63 |
Correct |
67 ms |
117868 KB |
Output is correct |
64 |
Correct |
68 ms |
117868 KB |
Output is correct |
65 |
Correct |
67 ms |
118124 KB |
Output is correct |
66 |
Correct |
65 ms |
118124 KB |
Output is correct |
67 |
Correct |
69 ms |
118232 KB |
Output is correct |
68 |
Correct |
66 ms |
118124 KB |
Output is correct |
69 |
Correct |
68 ms |
118124 KB |
Output is correct |
70 |
Correct |
66 ms |
118124 KB |
Output is correct |
71 |
Correct |
65 ms |
117868 KB |
Output is correct |
72 |
Correct |
64 ms |
117868 KB |
Output is correct |
73 |
Correct |
67 ms |
118124 KB |
Output is correct |
74 |
Correct |
65 ms |
118124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
117740 KB |
Output is correct |
2 |
Correct |
63 ms |
117740 KB |
Output is correct |
3 |
Correct |
63 ms |
117740 KB |
Output is correct |
4 |
Correct |
62 ms |
117840 KB |
Output is correct |
5 |
Correct |
64 ms |
117868 KB |
Output is correct |
6 |
Correct |
65 ms |
117740 KB |
Output is correct |
7 |
Correct |
63 ms |
117740 KB |
Output is correct |
8 |
Correct |
64 ms |
117740 KB |
Output is correct |
9 |
Correct |
63 ms |
117740 KB |
Output is correct |
10 |
Correct |
71 ms |
117740 KB |
Output is correct |
11 |
Correct |
72 ms |
117868 KB |
Output is correct |
12 |
Correct |
74 ms |
117740 KB |
Output is correct |
13 |
Correct |
64 ms |
117740 KB |
Output is correct |
14 |
Correct |
64 ms |
117740 KB |
Output is correct |
15 |
Correct |
64 ms |
117868 KB |
Output is correct |
16 |
Correct |
74 ms |
117784 KB |
Output is correct |
17 |
Correct |
66 ms |
117740 KB |
Output is correct |
18 |
Correct |
64 ms |
117740 KB |
Output is correct |
19 |
Correct |
64 ms |
117740 KB |
Output is correct |
20 |
Correct |
66 ms |
117740 KB |
Output is correct |
21 |
Correct |
64 ms |
117740 KB |
Output is correct |
22 |
Correct |
67 ms |
117740 KB |
Output is correct |
23 |
Correct |
64 ms |
117740 KB |
Output is correct |
24 |
Correct |
63 ms |
117740 KB |
Output is correct |
25 |
Correct |
64 ms |
117740 KB |
Output is correct |
26 |
Correct |
66 ms |
117740 KB |
Output is correct |
27 |
Correct |
64 ms |
117740 KB |
Output is correct |
28 |
Correct |
63 ms |
117740 KB |
Output is correct |
29 |
Correct |
70 ms |
117996 KB |
Output is correct |
30 |
Correct |
70 ms |
117740 KB |
Output is correct |
31 |
Correct |
67 ms |
117868 KB |
Output is correct |
32 |
Correct |
64 ms |
117740 KB |
Output is correct |
33 |
Correct |
64 ms |
117740 KB |
Output is correct |
34 |
Correct |
64 ms |
117952 KB |
Output is correct |
35 |
Correct |
65 ms |
117740 KB |
Output is correct |
36 |
Correct |
64 ms |
117740 KB |
Output is correct |
37 |
Correct |
64 ms |
117740 KB |
Output is correct |
38 |
Correct |
66 ms |
118124 KB |
Output is correct |
39 |
Correct |
64 ms |
118124 KB |
Output is correct |
40 |
Correct |
75 ms |
118124 KB |
Output is correct |
41 |
Correct |
67 ms |
118124 KB |
Output is correct |
42 |
Correct |
64 ms |
118124 KB |
Output is correct |
43 |
Correct |
64 ms |
118124 KB |
Output is correct |
44 |
Correct |
72 ms |
118124 KB |
Output is correct |
45 |
Correct |
66 ms |
118124 KB |
Output is correct |
46 |
Correct |
67 ms |
118124 KB |
Output is correct |
47 |
Correct |
67 ms |
118252 KB |
Output is correct |
48 |
Correct |
66 ms |
118124 KB |
Output is correct |
49 |
Correct |
65 ms |
118124 KB |
Output is correct |
50 |
Correct |
66 ms |
118124 KB |
Output is correct |
51 |
Correct |
65 ms |
118124 KB |
Output is correct |
52 |
Correct |
65 ms |
118124 KB |
Output is correct |
53 |
Correct |
67 ms |
118124 KB |
Output is correct |
54 |
Correct |
73 ms |
118124 KB |
Output is correct |
55 |
Correct |
66 ms |
118124 KB |
Output is correct |
56 |
Correct |
66 ms |
118124 KB |
Output is correct |
57 |
Correct |
65 ms |
118124 KB |
Output is correct |
58 |
Correct |
67 ms |
118124 KB |
Output is correct |
59 |
Correct |
67 ms |
117868 KB |
Output is correct |
60 |
Correct |
65 ms |
117868 KB |
Output is correct |
61 |
Correct |
64 ms |
117996 KB |
Output is correct |
62 |
Correct |
63 ms |
117868 KB |
Output is correct |
63 |
Correct |
67 ms |
117868 KB |
Output is correct |
64 |
Correct |
68 ms |
117868 KB |
Output is correct |
65 |
Correct |
67 ms |
118124 KB |
Output is correct |
66 |
Correct |
65 ms |
118124 KB |
Output is correct |
67 |
Correct |
69 ms |
118232 KB |
Output is correct |
68 |
Correct |
66 ms |
118124 KB |
Output is correct |
69 |
Correct |
68 ms |
118124 KB |
Output is correct |
70 |
Correct |
66 ms |
118124 KB |
Output is correct |
71 |
Correct |
65 ms |
117868 KB |
Output is correct |
72 |
Correct |
64 ms |
117868 KB |
Output is correct |
73 |
Correct |
67 ms |
118124 KB |
Output is correct |
74 |
Correct |
65 ms |
118124 KB |
Output is correct |
75 |
Correct |
1098 ms |
148460 KB |
Output is correct |
76 |
Correct |
1149 ms |
147516 KB |
Output is correct |
77 |
Correct |
1004 ms |
148460 KB |
Output is correct |
78 |
Correct |
1018 ms |
148972 KB |
Output is correct |
79 |
Correct |
583 ms |
148972 KB |
Output is correct |
80 |
Correct |
610 ms |
148076 KB |
Output is correct |
81 |
Correct |
586 ms |
131564 KB |
Output is correct |
82 |
Correct |
784 ms |
133612 KB |
Output is correct |
83 |
Correct |
693 ms |
132460 KB |
Output is correct |
84 |
Correct |
723 ms |
132844 KB |
Output is correct |
85 |
Correct |
609 ms |
131692 KB |
Output is correct |
86 |
Correct |
401 ms |
130412 KB |
Output is correct |
87 |
Correct |
434 ms |
130412 KB |
Output is correct |
88 |
Correct |
545 ms |
131180 KB |
Output is correct |
89 |
Correct |
509 ms |
131072 KB |
Output is correct |
90 |
Correct |
421 ms |
131064 KB |
Output is correct |
91 |
Correct |
342 ms |
129920 KB |
Output is correct |
92 |
Correct |
344 ms |
129900 KB |
Output is correct |
93 |
Correct |
382 ms |
130412 KB |
Output is correct |
94 |
Correct |
331 ms |
130540 KB |
Output is correct |
95 |
Correct |
411 ms |
131052 KB |
Output is correct |
96 |
Correct |
277 ms |
128492 KB |
Output is correct |
97 |
Correct |
295 ms |
129260 KB |
Output is correct |
98 |
Correct |
293 ms |
129132 KB |
Output is correct |
99 |
Correct |
281 ms |
129132 KB |
Output is correct |
100 |
Correct |
257 ms |
128492 KB |
Output is correct |
101 |
Correct |
254 ms |
128492 KB |
Output is correct |
102 |
Correct |
424 ms |
129004 KB |
Output is correct |
103 |
Correct |
410 ms |
128748 KB |
Output is correct |
104 |
Correct |
457 ms |
129388 KB |
Output is correct |
105 |
Correct |
377 ms |
129132 KB |
Output is correct |
106 |
Correct |
372 ms |
129516 KB |
Output is correct |
107 |
Correct |
336 ms |
129004 KB |
Output is correct |
108 |
Correct |
989 ms |
148492 KB |
Output is correct |
109 |
Correct |
908 ms |
150508 KB |
Output is correct |
110 |
Correct |
250 ms |
127980 KB |
Output is correct |
111 |
Correct |
301 ms |
128108 KB |
Output is correct |
112 |
Correct |
967 ms |
146028 KB |
Output is correct |
113 |
Correct |
605 ms |
150636 KB |
Output is correct |