#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 2e5+5;
vector< ii > vec;
int n, k;
int v[maxn];
int w[maxn];
struct node
{
ll sum;
int left, right;
node(){}
node(ll val, int left, int right) : sum(val), left(left), right(right){}
};
node cnt[20*maxn], tot[20*maxn];
int tungc = 0;
int tungd = 0;
int pos[maxn];
int rcnt[maxn], rtot[maxn];
int update(node *st, int &tung, int x, int dx, int p, int L, int R)
{
if(L<= x && x<= R)
{
if(L == R)
{
tung++;
st[tung] = node(st[p].sum+dx, 0, 0);
return tung;
}
int M = (L+R)/2;
int a = update(st, tung, x, dx, st[p].left, L, M);
int b = update(st, tung, x, dx, st[p].right, M+1, R);
tung++;
st[tung] = node(st[a].sum+st[b].sum, a, b);
return tung;
}
return p;
}
ll gimme(int p1, int p2, int p3, int p4, ll k, int L, int R)
{
if(L == R)
{
// printf("end at %d %lld\n", L, k);
if(k> 0) return tot[p4].sum-tot[p3].sum;
return 0;
}
int M = (L+R)/2;
ll here = (cnt[cnt[p2].right].sum)-(cnt[cnt[p1].right].sum);
// printf("%d %d right = %lld all %lld\n", L, R, here, cnt[p2].sum-cnt[p1].sum);
// printf("from %lld+%lld\n", cnt[cnt[p2].left].sum-cnt[cnt[p1].left].sum, cnt[cnt[p2].right].sum-cnt[cnt[p1].right].sum);
if(here>= k)
{
return gimme(cnt[p1].right, cnt[p2].right, tot[p3].right, tot[p4].right, k, M+1, R);
}
else
{
// printf("adding %lld\n", tot[tot[p4].right].sum-tot[tot[p3].right].sum);
return (tot[tot[p4].right].sum)-(tot[tot[p3].right].sum)+gimme(cnt[p1].left, cnt[p2].left, tot[p3].left, tot[p4].left, k-here, L, M);
}
}
ll cost(int x, int y)
{
// printf("querying %d %d\n", x, y);
return gimme(rcnt[x-1], rcnt[y], rtot[x-1], rtot[y], k-2, 1, n);
}
ll ret = -1e18;
void solve(int L, int R, int i, int j)
{
if(L> R) return;
int M = (L+R)/2;
pair<ll, int> best = {-1e18, i};
for(int p = i; p<= min(M-k+1, j); p++)
{
//[p..M]
// printf("cost[%d..%d] = %lld\n", p+1, M-1, cost(p+1, M-1));
best = max(best, {cost(p+1, M-1)+v[M]+v[p]-2LL*(w[M]-w[p]), p});
}
ret = max(ret, best.X);
solve(L, M-1, i, best.Y);
solve(M+1, R, best.Y, j);
}
int main()
{
scanf("%d %d", &n, &k);
vec.resize(n);
for(int i = 0; i< n; i++)
{
scanf("%d %d", &vec[i].Y, &vec[i].X);
}
sort(vec.begin(), vec.end());
for(int i = 1; i<= n; i++)
{
v[i] = vec[i-1].Y;
w[i] = vec[i-1].X;
}
cnt[0].sum = tot[0].sum = 0;
cnt[0].left = cnt[0].right = 0;
tot[0].left = tot[0].right = 0;
vector< ii > ayh;
for(int i = 1; i<= n; i++)
{
ayh.pb(ii(v[i], i));
}
sort(ayh.begin(), ayh.end());
for(int i = 0; i< n; i++)
{
pos[ayh[i].Y] = i+1;
}
// for(int i = 1; i<= n; i++) printf("%d %d\n", v[i], w[i]);
for(int i = 1; i<= n; i++)
{
// printf("updating %d\n", pos[i]);
rcnt[i] = update(cnt, tungc, pos[i], 1, rcnt[i-1], 1, n);
rtot[i] = update(tot, tungd, pos[i], v[i], rtot[i-1], 1, n);
}
// printf("done\n");
solve(1, n, 1, n);
// for(int i = 1; i<= n; i++)
// {
// for(int j = i+k-1; j<= n; j++)
// {
// ret = max(ret, cost(i+1, j-1)+v[i]+v[j]-2LL*(w[j]-w[i]));
// }
// }
printf("%lld\n", ret);
}
Compilation message
cake3.cpp: In function 'int main()':
cake3.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &k);
~~~~~^~~~~~~~~~~~~~~~~
cake3.cpp:111:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &vec[i].Y, &vec[i].X);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
380 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
380 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
396 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
380 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
376 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
380 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
380 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
396 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
380 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
376 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
38 |
Correct |
6 ms |
1144 KB |
Output is correct |
39 |
Correct |
6 ms |
1272 KB |
Output is correct |
40 |
Correct |
5 ms |
1180 KB |
Output is correct |
41 |
Correct |
5 ms |
1144 KB |
Output is correct |
42 |
Correct |
5 ms |
1272 KB |
Output is correct |
43 |
Correct |
5 ms |
1144 KB |
Output is correct |
44 |
Correct |
5 ms |
1144 KB |
Output is correct |
45 |
Correct |
6 ms |
1144 KB |
Output is correct |
46 |
Correct |
6 ms |
1276 KB |
Output is correct |
47 |
Correct |
6 ms |
1144 KB |
Output is correct |
48 |
Correct |
6 ms |
1196 KB |
Output is correct |
49 |
Correct |
5 ms |
1272 KB |
Output is correct |
50 |
Correct |
5 ms |
1272 KB |
Output is correct |
51 |
Correct |
5 ms |
1272 KB |
Output is correct |
52 |
Correct |
5 ms |
1144 KB |
Output is correct |
53 |
Correct |
5 ms |
1144 KB |
Output is correct |
54 |
Correct |
5 ms |
1272 KB |
Output is correct |
55 |
Correct |
5 ms |
1148 KB |
Output is correct |
56 |
Correct |
5 ms |
1144 KB |
Output is correct |
57 |
Correct |
5 ms |
1144 KB |
Output is correct |
58 |
Correct |
4 ms |
1144 KB |
Output is correct |
59 |
Correct |
4 ms |
1144 KB |
Output is correct |
60 |
Correct |
5 ms |
1144 KB |
Output is correct |
61 |
Correct |
4 ms |
1144 KB |
Output is correct |
62 |
Correct |
4 ms |
1144 KB |
Output is correct |
63 |
Correct |
5 ms |
1144 KB |
Output is correct |
64 |
Correct |
5 ms |
1272 KB |
Output is correct |
65 |
Correct |
5 ms |
1144 KB |
Output is correct |
66 |
Correct |
5 ms |
1144 KB |
Output is correct |
67 |
Correct |
6 ms |
1272 KB |
Output is correct |
68 |
Correct |
6 ms |
1272 KB |
Output is correct |
69 |
Correct |
5 ms |
1144 KB |
Output is correct |
70 |
Correct |
5 ms |
1272 KB |
Output is correct |
71 |
Correct |
5 ms |
1144 KB |
Output is correct |
72 |
Correct |
4 ms |
1144 KB |
Output is correct |
73 |
Correct |
5 ms |
1144 KB |
Output is correct |
74 |
Correct |
4 ms |
1144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
380 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
2 ms |
376 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
380 KB |
Output is correct |
10 |
Correct |
2 ms |
380 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
396 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
376 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
380 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
2 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
376 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
38 |
Correct |
6 ms |
1144 KB |
Output is correct |
39 |
Correct |
6 ms |
1272 KB |
Output is correct |
40 |
Correct |
5 ms |
1180 KB |
Output is correct |
41 |
Correct |
5 ms |
1144 KB |
Output is correct |
42 |
Correct |
5 ms |
1272 KB |
Output is correct |
43 |
Correct |
5 ms |
1144 KB |
Output is correct |
44 |
Correct |
5 ms |
1144 KB |
Output is correct |
45 |
Correct |
6 ms |
1144 KB |
Output is correct |
46 |
Correct |
6 ms |
1276 KB |
Output is correct |
47 |
Correct |
6 ms |
1144 KB |
Output is correct |
48 |
Correct |
6 ms |
1196 KB |
Output is correct |
49 |
Correct |
5 ms |
1272 KB |
Output is correct |
50 |
Correct |
5 ms |
1272 KB |
Output is correct |
51 |
Correct |
5 ms |
1272 KB |
Output is correct |
52 |
Correct |
5 ms |
1144 KB |
Output is correct |
53 |
Correct |
5 ms |
1144 KB |
Output is correct |
54 |
Correct |
5 ms |
1272 KB |
Output is correct |
55 |
Correct |
5 ms |
1148 KB |
Output is correct |
56 |
Correct |
5 ms |
1144 KB |
Output is correct |
57 |
Correct |
5 ms |
1144 KB |
Output is correct |
58 |
Correct |
4 ms |
1144 KB |
Output is correct |
59 |
Correct |
4 ms |
1144 KB |
Output is correct |
60 |
Correct |
5 ms |
1144 KB |
Output is correct |
61 |
Correct |
4 ms |
1144 KB |
Output is correct |
62 |
Correct |
4 ms |
1144 KB |
Output is correct |
63 |
Correct |
5 ms |
1144 KB |
Output is correct |
64 |
Correct |
5 ms |
1272 KB |
Output is correct |
65 |
Correct |
5 ms |
1144 KB |
Output is correct |
66 |
Correct |
5 ms |
1144 KB |
Output is correct |
67 |
Correct |
6 ms |
1272 KB |
Output is correct |
68 |
Correct |
6 ms |
1272 KB |
Output is correct |
69 |
Correct |
5 ms |
1144 KB |
Output is correct |
70 |
Correct |
5 ms |
1272 KB |
Output is correct |
71 |
Correct |
5 ms |
1144 KB |
Output is correct |
72 |
Correct |
4 ms |
1144 KB |
Output is correct |
73 |
Correct |
5 ms |
1144 KB |
Output is correct |
74 |
Correct |
4 ms |
1144 KB |
Output is correct |
75 |
Correct |
1102 ms |
119272 KB |
Output is correct |
76 |
Correct |
1171 ms |
115688 KB |
Output is correct |
77 |
Correct |
997 ms |
119400 KB |
Output is correct |
78 |
Correct |
1056 ms |
121396 KB |
Output is correct |
79 |
Correct |
443 ms |
122052 KB |
Output is correct |
80 |
Correct |
511 ms |
118032 KB |
Output is correct |
81 |
Correct |
862 ms |
119872 KB |
Output is correct |
82 |
Correct |
1034 ms |
121524 KB |
Output is correct |
83 |
Correct |
989 ms |
125772 KB |
Output is correct |
84 |
Correct |
1054 ms |
125500 KB |
Output is correct |
85 |
Correct |
888 ms |
120892 KB |
Output is correct |
86 |
Correct |
559 ms |
116584 KB |
Output is correct |
87 |
Correct |
577 ms |
114972 KB |
Output is correct |
88 |
Correct |
784 ms |
114316 KB |
Output is correct |
89 |
Correct |
767 ms |
120856 KB |
Output is correct |
90 |
Correct |
589 ms |
126828 KB |
Output is correct |
91 |
Correct |
474 ms |
116736 KB |
Output is correct |
92 |
Correct |
475 ms |
115816 KB |
Output is correct |
93 |
Correct |
537 ms |
121108 KB |
Output is correct |
94 |
Correct |
498 ms |
126664 KB |
Output is correct |
95 |
Correct |
589 ms |
126952 KB |
Output is correct |
96 |
Correct |
383 ms |
117372 KB |
Output is correct |
97 |
Correct |
416 ms |
127168 KB |
Output is correct |
98 |
Correct |
419 ms |
125160 KB |
Output is correct |
99 |
Correct |
393 ms |
125436 KB |
Output is correct |
100 |
Correct |
349 ms |
117864 KB |
Output is correct |
101 |
Correct |
356 ms |
117828 KB |
Output is correct |
102 |
Correct |
861 ms |
118000 KB |
Output is correct |
103 |
Correct |
765 ms |
116196 KB |
Output is correct |
104 |
Correct |
909 ms |
123024 KB |
Output is correct |
105 |
Correct |
717 ms |
122556 KB |
Output is correct |
106 |
Correct |
743 ms |
125816 KB |
Output is correct |
107 |
Correct |
646 ms |
121208 KB |
Output is correct |
108 |
Correct |
1012 ms |
120460 KB |
Output is correct |
109 |
Correct |
861 ms |
128168 KB |
Output is correct |
110 |
Correct |
407 ms |
118172 KB |
Output is correct |
111 |
Correct |
498 ms |
119484 KB |
Output is correct |
112 |
Correct |
389 ms |
113704 KB |
Output is correct |
113 |
Correct |
473 ms |
128428 KB |
Output is correct |