#include <bits/stdc++.h>
#define pii pair<long long, long long>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10;
int n, m, ver[N];
pii cake[N];
vector<long long> t, coord;
vector<int> sz, L, R;
unordered_map<long long, int> mp;
long long ans[N], ret = -2e18;
int newleaf( long long va, int ss ) {
t.emplace_back( va ), sz.emplace_back( ss ), L.emplace_back( -1 ), R.emplace_back( -1 );
return (int)t.size() - 1;
}
int newpar( int l, int r ) {
t.emplace_back( t[l] + t[r] ), sz.emplace_back( sz[l] + sz[r] );
L.emplace_back( l ), R.emplace_back( r );
return (int)t.size() - 1;
}
int get( long long x ) {
mp[x]++;
return lower_bound( coord.begin(), coord.end(), x ) - coord.begin() + mp[x];
}
int build( int l = 1, int r = coord.size() ) {
if( l == r ) return newleaf( 0, 0 );
int mid = l + r >> 1;
return newpar( build( l, mid ), build( mid+1, r ) );
}
int update( int x, long long va, int p, int l = 1, int r = coord.size() ) {
if( l == r ) return newleaf( va, 1 );
int mid = l + r >> 1;
if( mid >= x ) return newpar( update( x, va, L[p], l, mid ), R[p] );
else return newpar( L[p], update( x, va, R[p], mid+1, r ) );
}
long long query( int a, int b, int x, int l = 1, int r = coord.size() ) {
if( x == 0 ) return 0LL;
if( l == r ) return t[b] - t[a];
int mid = l + r >> 1;
if( sz[R[b]] - sz[R[a]] >= x ) return query( R[a], R[b], x, mid+1, r );
else return t[R[b]] - t[R[a]] + query( L[a], L[b], x - sz[R[b]] + sz[R[a]], l, mid );
}
void solve( int l, int r, int optl, int optr ) {
if( l > r ) return ;
int mid = l + r >> 1, idx = optl;
for( int i = max( mid + m - 1, optl ) ; i <= optr ; i++ ) {
long long now = query( ver[mid], ver[i-1], m-2 ) + cake[i].x + cake[mid].x - 2*cake[i].y + 2*cake[mid].y;
if( now > ans[mid] ) ans[mid] = now, idx = i;
}
solve( l, mid-1, optl, idx ), solve( mid+1, r, idx, optr );
}
int main()
{
fill_n( ans, N, -2e18 );
t.emplace_back( 0 ), sz.emplace_back( 0 ), R.emplace_back( 0 ), L.emplace_back( 0 );
scanf("%d %d",&n,&m);
for( int i = 1 ; i <= n ; i++ ) {
scanf("%lld %lld",&cake[i].x,&cake[i].y);
coord.emplace_back( cake[i].x );
}
sort( cake + 1, cake + 1 + n, [&]( const pii &a, const pii &b ) {
return a.y < b.y;
});
sort( coord.begin(), coord.end() );
ver[0] = build();
//for( int i = 1 ; i < L.size() ; i++ ) printf("%d %d\n",L[i],R[i]);
for( int i = 1 ; i <= n ; i++ ) ver[i] = update( get( cake[i].x ), cake[i].x, ver[i-1] );
solve( 1, n-m+1, 1, n );
for( int i = 1 ; i <= n-m+1 ; i++ ) {
//printf("%lld\n",ans[i]);
ret = max( ret, ans[i] );
}
printf("%lld",ret);
return 0;
}
Compilation message
cake3.cpp: In function 'int build(int, int)':
cake3.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
cake3.cpp: In function 'int update(int, long long int, int, int, int)':
cake3.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
cake3.cpp: In function 'long long int query(int, int, int, int, int)':
cake3.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1;
~~^~~
cake3.cpp: In function 'void solve(int, int, int, int)':
cake3.cpp:56:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid = l + r >> 1, idx = optl;
~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&m);
~~~~~^~~~~~~~~~~~~~~
cake3.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld",&cake[i].x,&cake[i].y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1920 KB |
Output is correct |
2 |
Correct |
5 ms |
1920 KB |
Output is correct |
3 |
Correct |
5 ms |
1920 KB |
Output is correct |
4 |
Correct |
5 ms |
1920 KB |
Output is correct |
5 |
Correct |
5 ms |
1920 KB |
Output is correct |
6 |
Correct |
5 ms |
1920 KB |
Output is correct |
7 |
Correct |
6 ms |
1920 KB |
Output is correct |
8 |
Correct |
5 ms |
1920 KB |
Output is correct |
9 |
Correct |
6 ms |
1920 KB |
Output is correct |
10 |
Correct |
5 ms |
1920 KB |
Output is correct |
11 |
Correct |
6 ms |
1920 KB |
Output is correct |
12 |
Correct |
6 ms |
1920 KB |
Output is correct |
13 |
Correct |
6 ms |
1920 KB |
Output is correct |
14 |
Correct |
6 ms |
1920 KB |
Output is correct |
15 |
Correct |
7 ms |
1920 KB |
Output is correct |
16 |
Correct |
6 ms |
1920 KB |
Output is correct |
17 |
Correct |
6 ms |
1920 KB |
Output is correct |
18 |
Correct |
5 ms |
1920 KB |
Output is correct |
19 |
Correct |
5 ms |
1920 KB |
Output is correct |
20 |
Correct |
5 ms |
1920 KB |
Output is correct |
21 |
Correct |
5 ms |
1920 KB |
Output is correct |
22 |
Correct |
6 ms |
1920 KB |
Output is correct |
23 |
Correct |
5 ms |
1920 KB |
Output is correct |
24 |
Correct |
5 ms |
1920 KB |
Output is correct |
25 |
Correct |
6 ms |
1920 KB |
Output is correct |
26 |
Correct |
5 ms |
1920 KB |
Output is correct |
27 |
Correct |
5 ms |
1920 KB |
Output is correct |
28 |
Correct |
5 ms |
1920 KB |
Output is correct |
29 |
Correct |
6 ms |
1920 KB |
Output is correct |
30 |
Correct |
5 ms |
1920 KB |
Output is correct |
31 |
Correct |
6 ms |
1920 KB |
Output is correct |
32 |
Correct |
5 ms |
1920 KB |
Output is correct |
33 |
Correct |
6 ms |
1920 KB |
Output is correct |
34 |
Correct |
5 ms |
1920 KB |
Output is correct |
35 |
Correct |
5 ms |
1920 KB |
Output is correct |
36 |
Correct |
6 ms |
1920 KB |
Output is correct |
37 |
Correct |
6 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1920 KB |
Output is correct |
2 |
Correct |
5 ms |
1920 KB |
Output is correct |
3 |
Correct |
5 ms |
1920 KB |
Output is correct |
4 |
Correct |
5 ms |
1920 KB |
Output is correct |
5 |
Correct |
5 ms |
1920 KB |
Output is correct |
6 |
Correct |
5 ms |
1920 KB |
Output is correct |
7 |
Correct |
6 ms |
1920 KB |
Output is correct |
8 |
Correct |
5 ms |
1920 KB |
Output is correct |
9 |
Correct |
6 ms |
1920 KB |
Output is correct |
10 |
Correct |
5 ms |
1920 KB |
Output is correct |
11 |
Correct |
6 ms |
1920 KB |
Output is correct |
12 |
Correct |
6 ms |
1920 KB |
Output is correct |
13 |
Correct |
6 ms |
1920 KB |
Output is correct |
14 |
Correct |
6 ms |
1920 KB |
Output is correct |
15 |
Correct |
7 ms |
1920 KB |
Output is correct |
16 |
Correct |
6 ms |
1920 KB |
Output is correct |
17 |
Correct |
6 ms |
1920 KB |
Output is correct |
18 |
Correct |
5 ms |
1920 KB |
Output is correct |
19 |
Correct |
5 ms |
1920 KB |
Output is correct |
20 |
Correct |
5 ms |
1920 KB |
Output is correct |
21 |
Correct |
5 ms |
1920 KB |
Output is correct |
22 |
Correct |
6 ms |
1920 KB |
Output is correct |
23 |
Correct |
5 ms |
1920 KB |
Output is correct |
24 |
Correct |
5 ms |
1920 KB |
Output is correct |
25 |
Correct |
6 ms |
1920 KB |
Output is correct |
26 |
Correct |
5 ms |
1920 KB |
Output is correct |
27 |
Correct |
5 ms |
1920 KB |
Output is correct |
28 |
Correct |
5 ms |
1920 KB |
Output is correct |
29 |
Correct |
6 ms |
1920 KB |
Output is correct |
30 |
Correct |
5 ms |
1920 KB |
Output is correct |
31 |
Correct |
6 ms |
1920 KB |
Output is correct |
32 |
Correct |
5 ms |
1920 KB |
Output is correct |
33 |
Correct |
6 ms |
1920 KB |
Output is correct |
34 |
Correct |
5 ms |
1920 KB |
Output is correct |
35 |
Correct |
5 ms |
1920 KB |
Output is correct |
36 |
Correct |
6 ms |
1920 KB |
Output is correct |
37 |
Correct |
6 ms |
1920 KB |
Output is correct |
38 |
Correct |
9 ms |
2684 KB |
Output is correct |
39 |
Correct |
9 ms |
2812 KB |
Output is correct |
40 |
Correct |
9 ms |
2812 KB |
Output is correct |
41 |
Correct |
8 ms |
2812 KB |
Output is correct |
42 |
Correct |
9 ms |
2812 KB |
Output is correct |
43 |
Correct |
8 ms |
2684 KB |
Output is correct |
44 |
Correct |
8 ms |
2684 KB |
Output is correct |
45 |
Correct |
9 ms |
2812 KB |
Output is correct |
46 |
Correct |
9 ms |
2812 KB |
Output is correct |
47 |
Correct |
9 ms |
2812 KB |
Output is correct |
48 |
Correct |
8 ms |
2684 KB |
Output is correct |
49 |
Correct |
9 ms |
2812 KB |
Output is correct |
50 |
Correct |
8 ms |
2812 KB |
Output is correct |
51 |
Correct |
9 ms |
2812 KB |
Output is correct |
52 |
Correct |
8 ms |
2684 KB |
Output is correct |
53 |
Correct |
8 ms |
2812 KB |
Output is correct |
54 |
Correct |
8 ms |
2812 KB |
Output is correct |
55 |
Correct |
8 ms |
2812 KB |
Output is correct |
56 |
Correct |
8 ms |
2812 KB |
Output is correct |
57 |
Correct |
8 ms |
2812 KB |
Output is correct |
58 |
Correct |
8 ms |
2812 KB |
Output is correct |
59 |
Correct |
7 ms |
2684 KB |
Output is correct |
60 |
Correct |
8 ms |
2684 KB |
Output is correct |
61 |
Correct |
8 ms |
2684 KB |
Output is correct |
62 |
Correct |
7 ms |
2684 KB |
Output is correct |
63 |
Correct |
7 ms |
2684 KB |
Output is correct |
64 |
Correct |
8 ms |
2684 KB |
Output is correct |
65 |
Correct |
8 ms |
2812 KB |
Output is correct |
66 |
Correct |
9 ms |
2812 KB |
Output is correct |
67 |
Correct |
9 ms |
2812 KB |
Output is correct |
68 |
Correct |
8 ms |
2812 KB |
Output is correct |
69 |
Correct |
8 ms |
2812 KB |
Output is correct |
70 |
Correct |
8 ms |
2812 KB |
Output is correct |
71 |
Correct |
8 ms |
2684 KB |
Output is correct |
72 |
Correct |
7 ms |
2684 KB |
Output is correct |
73 |
Correct |
9 ms |
2684 KB |
Output is correct |
74 |
Correct |
8 ms |
2812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1920 KB |
Output is correct |
2 |
Correct |
5 ms |
1920 KB |
Output is correct |
3 |
Correct |
5 ms |
1920 KB |
Output is correct |
4 |
Correct |
5 ms |
1920 KB |
Output is correct |
5 |
Correct |
5 ms |
1920 KB |
Output is correct |
6 |
Correct |
5 ms |
1920 KB |
Output is correct |
7 |
Correct |
6 ms |
1920 KB |
Output is correct |
8 |
Correct |
5 ms |
1920 KB |
Output is correct |
9 |
Correct |
6 ms |
1920 KB |
Output is correct |
10 |
Correct |
5 ms |
1920 KB |
Output is correct |
11 |
Correct |
6 ms |
1920 KB |
Output is correct |
12 |
Correct |
6 ms |
1920 KB |
Output is correct |
13 |
Correct |
6 ms |
1920 KB |
Output is correct |
14 |
Correct |
6 ms |
1920 KB |
Output is correct |
15 |
Correct |
7 ms |
1920 KB |
Output is correct |
16 |
Correct |
6 ms |
1920 KB |
Output is correct |
17 |
Correct |
6 ms |
1920 KB |
Output is correct |
18 |
Correct |
5 ms |
1920 KB |
Output is correct |
19 |
Correct |
5 ms |
1920 KB |
Output is correct |
20 |
Correct |
5 ms |
1920 KB |
Output is correct |
21 |
Correct |
5 ms |
1920 KB |
Output is correct |
22 |
Correct |
6 ms |
1920 KB |
Output is correct |
23 |
Correct |
5 ms |
1920 KB |
Output is correct |
24 |
Correct |
5 ms |
1920 KB |
Output is correct |
25 |
Correct |
6 ms |
1920 KB |
Output is correct |
26 |
Correct |
5 ms |
1920 KB |
Output is correct |
27 |
Correct |
5 ms |
1920 KB |
Output is correct |
28 |
Correct |
5 ms |
1920 KB |
Output is correct |
29 |
Correct |
6 ms |
1920 KB |
Output is correct |
30 |
Correct |
5 ms |
1920 KB |
Output is correct |
31 |
Correct |
6 ms |
1920 KB |
Output is correct |
32 |
Correct |
5 ms |
1920 KB |
Output is correct |
33 |
Correct |
6 ms |
1920 KB |
Output is correct |
34 |
Correct |
5 ms |
1920 KB |
Output is correct |
35 |
Correct |
5 ms |
1920 KB |
Output is correct |
36 |
Correct |
6 ms |
1920 KB |
Output is correct |
37 |
Correct |
6 ms |
1920 KB |
Output is correct |
38 |
Correct |
9 ms |
2684 KB |
Output is correct |
39 |
Correct |
9 ms |
2812 KB |
Output is correct |
40 |
Correct |
9 ms |
2812 KB |
Output is correct |
41 |
Correct |
8 ms |
2812 KB |
Output is correct |
42 |
Correct |
9 ms |
2812 KB |
Output is correct |
43 |
Correct |
8 ms |
2684 KB |
Output is correct |
44 |
Correct |
8 ms |
2684 KB |
Output is correct |
45 |
Correct |
9 ms |
2812 KB |
Output is correct |
46 |
Correct |
9 ms |
2812 KB |
Output is correct |
47 |
Correct |
9 ms |
2812 KB |
Output is correct |
48 |
Correct |
8 ms |
2684 KB |
Output is correct |
49 |
Correct |
9 ms |
2812 KB |
Output is correct |
50 |
Correct |
8 ms |
2812 KB |
Output is correct |
51 |
Correct |
9 ms |
2812 KB |
Output is correct |
52 |
Correct |
8 ms |
2684 KB |
Output is correct |
53 |
Correct |
8 ms |
2812 KB |
Output is correct |
54 |
Correct |
8 ms |
2812 KB |
Output is correct |
55 |
Correct |
8 ms |
2812 KB |
Output is correct |
56 |
Correct |
8 ms |
2812 KB |
Output is correct |
57 |
Correct |
8 ms |
2812 KB |
Output is correct |
58 |
Correct |
8 ms |
2812 KB |
Output is correct |
59 |
Correct |
7 ms |
2684 KB |
Output is correct |
60 |
Correct |
8 ms |
2684 KB |
Output is correct |
61 |
Correct |
8 ms |
2684 KB |
Output is correct |
62 |
Correct |
7 ms |
2684 KB |
Output is correct |
63 |
Correct |
7 ms |
2684 KB |
Output is correct |
64 |
Correct |
8 ms |
2684 KB |
Output is correct |
65 |
Correct |
8 ms |
2812 KB |
Output is correct |
66 |
Correct |
9 ms |
2812 KB |
Output is correct |
67 |
Correct |
9 ms |
2812 KB |
Output is correct |
68 |
Correct |
8 ms |
2812 KB |
Output is correct |
69 |
Correct |
8 ms |
2812 KB |
Output is correct |
70 |
Correct |
8 ms |
2812 KB |
Output is correct |
71 |
Correct |
8 ms |
2684 KB |
Output is correct |
72 |
Correct |
7 ms |
2684 KB |
Output is correct |
73 |
Correct |
9 ms |
2684 KB |
Output is correct |
74 |
Correct |
8 ms |
2812 KB |
Output is correct |
75 |
Correct |
1038 ms |
107848 KB |
Output is correct |
76 |
Correct |
1065 ms |
106016 KB |
Output is correct |
77 |
Correct |
959 ms |
108188 KB |
Output is correct |
78 |
Correct |
1020 ms |
109084 KB |
Output is correct |
79 |
Correct |
553 ms |
109392 KB |
Output is correct |
80 |
Correct |
608 ms |
107292 KB |
Output is correct |
81 |
Correct |
978 ms |
107920 KB |
Output is correct |
82 |
Correct |
1139 ms |
108924 KB |
Output is correct |
83 |
Correct |
1080 ms |
111252 KB |
Output is correct |
84 |
Correct |
1121 ms |
111032 KB |
Output is correct |
85 |
Correct |
1002 ms |
108456 KB |
Output is correct |
86 |
Correct |
629 ms |
106092 KB |
Output is correct |
87 |
Correct |
684 ms |
105140 KB |
Output is correct |
88 |
Correct |
888 ms |
104732 KB |
Output is correct |
89 |
Correct |
924 ms |
108524 KB |
Output is correct |
90 |
Correct |
728 ms |
111816 KB |
Output is correct |
91 |
Correct |
552 ms |
106140 KB |
Output is correct |
92 |
Correct |
583 ms |
105500 KB |
Output is correct |
93 |
Correct |
609 ms |
108624 KB |
Output is correct |
94 |
Correct |
637 ms |
111644 KB |
Output is correct |
95 |
Correct |
653 ms |
111840 KB |
Output is correct |
96 |
Correct |
354 ms |
102172 KB |
Output is correct |
97 |
Correct |
359 ms |
107804 KB |
Output is correct |
98 |
Correct |
378 ms |
106908 KB |
Output is correct |
99 |
Correct |
348 ms |
106924 KB |
Output is correct |
100 |
Correct |
308 ms |
102556 KB |
Output is correct |
101 |
Correct |
316 ms |
102684 KB |
Output is correct |
102 |
Correct |
739 ms |
102556 KB |
Output is correct |
103 |
Correct |
694 ms |
101792 KB |
Output is correct |
104 |
Correct |
750 ms |
105628 KB |
Output is correct |
105 |
Correct |
670 ms |
105372 KB |
Output is correct |
106 |
Correct |
661 ms |
107292 KB |
Output is correct |
107 |
Correct |
536 ms |
104476 KB |
Output is correct |
108 |
Correct |
976 ms |
108572 KB |
Output is correct |
109 |
Correct |
918 ms |
112948 KB |
Output is correct |
110 |
Correct |
328 ms |
102428 KB |
Output is correct |
111 |
Correct |
396 ms |
103452 KB |
Output is correct |
112 |
Correct |
954 ms |
104220 KB |
Output is correct |
113 |
Correct |
582 ms |
113180 KB |
Output is correct |