# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
545609 |
2022-04-05T00:44:20 Z |
chonka |
Cake 3 (JOI19_cake3) |
C++ |
|
1133 ms |
202348 KB |
#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
// mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
#define MAXN 200007
const ll inf = 1e17 ;
int n , k ;
pair < int , int > a[ MAXN ] ;
pair < int , int > srt[ MAXN ] ;
int ord[ MAXN ] ;
struct node {
ll sm ;
int cnt ;
node *pl , *pr ;
node ( ) { sm = cnt = 0 ; pl = pr = NULL ; }
node ( node *_pl , node *_pr ) {
pl = _pl ; pr = _pr ;
sm = 0 ; cnt = 0 ;
if ( pl != NULL ) {
sm += pl->sm ;
cnt += pl->cnt ;
}
if ( pr != NULL ) {
sm += pr->sm ;
cnt += pr->cnt ;
}
}
};
node* root[ MAXN ] ;
node* init ( int l , int r ) {
if ( l == r ) { return new node ( ) ; }
int mid = ( l + r ) / 2 ;
node *ret = new node ( init ( l , mid ) , init ( mid + 1 , r ) ) ;
return ret ;
}
node* update ( node *w , int l , int r , int pos , int add ) {
if ( l == r ) {
node *ret = new node ( ) ;
++ ret->cnt ;
ret->sm += add ;
return ret ;
}
int mid = ( l + r ) / 2 ;
if ( pos <= mid ) {
return new node ( update ( w->pl , l , mid , pos , add ) , w->pr ) ;
}
else {
return new node ( w->pl , update ( w->pr , mid + 1 , r , pos , add ) ) ;
}
}
pair < ll , int > query ( node *st , node *en , int l , int r , int lft ) {
if ( lft == 0 ) { return { 0 , 0 } ; }
if ( en->cnt - st->cnt <= lft ) {
return { en->sm - st->sm , en->cnt - st->cnt } ;
}
int mid = ( l + r ) / 2 ;
pair < ll , int > ret1 = query ( st->pr , en->pr , mid + 1 , r , lft ) ;
pair < ll , int > ret2 = query ( st->pl , en->pl , l , mid , lft - ret1.second ) ;
return { ret1.first + ret2.first , ret1.second + ret2.second } ;
}
ll ans[ MAXN ] ;
ll calc ( int x , int y ) {
if ( y - x - 1 < k - 2 ) { return -inf ; }
ll ret = 2 * ( a[ x ].second - a[ y ].second ) ;
ret += a[ x ].first + a[ y ].first ;
pair < ll , int > hh = query ( root[ x ] , root[ y - 1 ] , 1 , n , k - 2 ) ;
ret += hh.first ;
return ret ;
}
void f ( int l , int r , int st , int en ) {
if ( l > r ) { return ; }
int mid = ( l + r ) / 2 ;
int wh = -1 ;
for ( int i = max ( mid + k - 1 , st ) ; i <= en ; ++ i ) {
ll cand = calc ( mid , i ) ;
if ( ans[ mid ] <= cand ) {
ans[ mid ] = cand ;
wh = i ;
}
}
if ( l < mid ) {
f ( l , mid - 1 , st , wh ) ;
}
if ( mid < r ) {
f ( mid + 1 , r , wh , en ) ;
}
}
void input ( ) {
cin >> n >> k ;
for ( int i = 1 ; i <= n ; ++ i ) {
cin >> a[ i ].first >> a[ i ].second ;
}
auto cmp = [ & ] ( pair < int , int > p1 , pair < int , int > p2 ) {
if ( p1.second != p2.second ) { return ( p1.second < p2.second ) ; }
return p1.first < p2.first ;
};
sort ( a + 1 , a + n + 1 , cmp ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
srt[ i ] = { a[ i ].first , i } ;
}
sort ( srt + 1 , srt + n + 1 ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
ord[ srt[ i ].second ] = i ;
}
}
void solve ( ) {
root[ 0 ] = init ( 1 , n ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
root[ i ] = update ( root[ i - 1 ] , 1 , n , ord[ i ] , a[ i ].first ) ;
}
for ( int i = 1 ; i <= n - k + 1 ; ++ i ) {
ans[ i ] = -inf ;
}
f ( 1 , n - k + 1 , 1 , n ) ;
ll ret = -inf ;
for ( int i = 1 ; i <= n - k + 1 ; ++ i ) {
ret = max ( ret , ans[ i ] ) ;
}
cout << ret << "\n" ;
}
int main ( ) {
ios_base :: sync_with_stdio ( false ) ;
cin.tie ( NULL ) ;
int t = 1 ;
// cin >> t ;
while ( t -- ) {
input ( ) ;
solve ( ) ;
}
return 0 ;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
352 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
0 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
0 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
0 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
352 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
0 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
0 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
0 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
38 |
Correct |
3 ms |
1620 KB |
Output is correct |
39 |
Correct |
4 ms |
1620 KB |
Output is correct |
40 |
Correct |
3 ms |
1620 KB |
Output is correct |
41 |
Correct |
3 ms |
1620 KB |
Output is correct |
42 |
Correct |
4 ms |
1620 KB |
Output is correct |
43 |
Correct |
3 ms |
1584 KB |
Output is correct |
44 |
Correct |
3 ms |
1492 KB |
Output is correct |
45 |
Correct |
5 ms |
1620 KB |
Output is correct |
46 |
Correct |
4 ms |
1620 KB |
Output is correct |
47 |
Correct |
4 ms |
1620 KB |
Output is correct |
48 |
Correct |
3 ms |
1492 KB |
Output is correct |
49 |
Correct |
3 ms |
1620 KB |
Output is correct |
50 |
Correct |
4 ms |
1620 KB |
Output is correct |
51 |
Correct |
3 ms |
1620 KB |
Output is correct |
52 |
Correct |
3 ms |
1620 KB |
Output is correct |
53 |
Correct |
3 ms |
1620 KB |
Output is correct |
54 |
Correct |
3 ms |
1620 KB |
Output is correct |
55 |
Correct |
3 ms |
1620 KB |
Output is correct |
56 |
Correct |
3 ms |
1620 KB |
Output is correct |
57 |
Correct |
2 ms |
1620 KB |
Output is correct |
58 |
Correct |
3 ms |
1620 KB |
Output is correct |
59 |
Correct |
3 ms |
1492 KB |
Output is correct |
60 |
Correct |
3 ms |
1620 KB |
Output is correct |
61 |
Correct |
3 ms |
1620 KB |
Output is correct |
62 |
Correct |
4 ms |
1620 KB |
Output is correct |
63 |
Correct |
5 ms |
1620 KB |
Output is correct |
64 |
Correct |
3 ms |
1620 KB |
Output is correct |
65 |
Correct |
4 ms |
1620 KB |
Output is correct |
66 |
Correct |
3 ms |
1620 KB |
Output is correct |
67 |
Correct |
3 ms |
1620 KB |
Output is correct |
68 |
Correct |
3 ms |
1620 KB |
Output is correct |
69 |
Correct |
3 ms |
1620 KB |
Output is correct |
70 |
Correct |
3 ms |
1620 KB |
Output is correct |
71 |
Correct |
3 ms |
1620 KB |
Output is correct |
72 |
Correct |
2 ms |
1620 KB |
Output is correct |
73 |
Correct |
3 ms |
1620 KB |
Output is correct |
74 |
Correct |
2 ms |
1620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
352 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
0 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
384 KB |
Output is correct |
26 |
Correct |
0 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
340 KB |
Output is correct |
28 |
Correct |
1 ms |
340 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
0 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
0 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
340 KB |
Output is correct |
34 |
Correct |
0 ms |
340 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
0 ms |
340 KB |
Output is correct |
38 |
Correct |
3 ms |
1620 KB |
Output is correct |
39 |
Correct |
4 ms |
1620 KB |
Output is correct |
40 |
Correct |
3 ms |
1620 KB |
Output is correct |
41 |
Correct |
3 ms |
1620 KB |
Output is correct |
42 |
Correct |
4 ms |
1620 KB |
Output is correct |
43 |
Correct |
3 ms |
1584 KB |
Output is correct |
44 |
Correct |
3 ms |
1492 KB |
Output is correct |
45 |
Correct |
5 ms |
1620 KB |
Output is correct |
46 |
Correct |
4 ms |
1620 KB |
Output is correct |
47 |
Correct |
4 ms |
1620 KB |
Output is correct |
48 |
Correct |
3 ms |
1492 KB |
Output is correct |
49 |
Correct |
3 ms |
1620 KB |
Output is correct |
50 |
Correct |
4 ms |
1620 KB |
Output is correct |
51 |
Correct |
3 ms |
1620 KB |
Output is correct |
52 |
Correct |
3 ms |
1620 KB |
Output is correct |
53 |
Correct |
3 ms |
1620 KB |
Output is correct |
54 |
Correct |
3 ms |
1620 KB |
Output is correct |
55 |
Correct |
3 ms |
1620 KB |
Output is correct |
56 |
Correct |
3 ms |
1620 KB |
Output is correct |
57 |
Correct |
2 ms |
1620 KB |
Output is correct |
58 |
Correct |
3 ms |
1620 KB |
Output is correct |
59 |
Correct |
3 ms |
1492 KB |
Output is correct |
60 |
Correct |
3 ms |
1620 KB |
Output is correct |
61 |
Correct |
3 ms |
1620 KB |
Output is correct |
62 |
Correct |
4 ms |
1620 KB |
Output is correct |
63 |
Correct |
5 ms |
1620 KB |
Output is correct |
64 |
Correct |
3 ms |
1620 KB |
Output is correct |
65 |
Correct |
4 ms |
1620 KB |
Output is correct |
66 |
Correct |
3 ms |
1620 KB |
Output is correct |
67 |
Correct |
3 ms |
1620 KB |
Output is correct |
68 |
Correct |
3 ms |
1620 KB |
Output is correct |
69 |
Correct |
3 ms |
1620 KB |
Output is correct |
70 |
Correct |
3 ms |
1620 KB |
Output is correct |
71 |
Correct |
3 ms |
1620 KB |
Output is correct |
72 |
Correct |
2 ms |
1620 KB |
Output is correct |
73 |
Correct |
3 ms |
1620 KB |
Output is correct |
74 |
Correct |
2 ms |
1620 KB |
Output is correct |
75 |
Correct |
1027 ms |
186576 KB |
Output is correct |
76 |
Correct |
1133 ms |
182916 KB |
Output is correct |
77 |
Correct |
884 ms |
188356 KB |
Output is correct |
78 |
Correct |
937 ms |
191404 KB |
Output is correct |
79 |
Correct |
346 ms |
191184 KB |
Output is correct |
80 |
Correct |
415 ms |
185480 KB |
Output is correct |
81 |
Correct |
836 ms |
190332 KB |
Output is correct |
82 |
Correct |
1008 ms |
193208 KB |
Output is correct |
83 |
Correct |
932 ms |
199736 KB |
Output is correct |
84 |
Correct |
964 ms |
199160 KB |
Output is correct |
85 |
Correct |
788 ms |
191888 KB |
Output is correct |
86 |
Correct |
547 ms |
184908 KB |
Output is correct |
87 |
Correct |
632 ms |
182472 KB |
Output is correct |
88 |
Correct |
756 ms |
181308 KB |
Output is correct |
89 |
Correct |
811 ms |
191972 KB |
Output is correct |
90 |
Correct |
640 ms |
201040 KB |
Output is correct |
91 |
Correct |
456 ms |
185040 KB |
Output is correct |
92 |
Correct |
488 ms |
183688 KB |
Output is correct |
93 |
Correct |
519 ms |
191920 KB |
Output is correct |
94 |
Correct |
519 ms |
200648 KB |
Output is correct |
95 |
Correct |
618 ms |
201432 KB |
Output is correct |
96 |
Correct |
593 ms |
186720 KB |
Output is correct |
97 |
Correct |
699 ms |
202348 KB |
Output is correct |
98 |
Correct |
653 ms |
199168 KB |
Output is correct |
99 |
Correct |
614 ms |
199628 KB |
Output is correct |
100 |
Correct |
492 ms |
187640 KB |
Output is correct |
101 |
Correct |
477 ms |
187584 KB |
Output is correct |
102 |
Correct |
891 ms |
188032 KB |
Output is correct |
103 |
Correct |
796 ms |
185308 KB |
Output is correct |
104 |
Correct |
1022 ms |
195980 KB |
Output is correct |
105 |
Correct |
791 ms |
195000 KB |
Output is correct |
106 |
Correct |
807 ms |
200192 KB |
Output is correct |
107 |
Correct |
692 ms |
192764 KB |
Output is correct |
108 |
Correct |
898 ms |
190356 KB |
Output is correct |
109 |
Correct |
801 ms |
202136 KB |
Output is correct |
110 |
Correct |
401 ms |
188660 KB |
Output is correct |
111 |
Correct |
499 ms |
191168 KB |
Output is correct |
112 |
Correct |
802 ms |
181868 KB |
Output is correct |
113 |
Correct |
408 ms |
201504 KB |
Output is correct |