# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
333107 |
2020-12-04T14:46:09 Z |
CaroLinda |
Cake 3 (JOI19_cake3) |
C++14 |
|
1064 ms |
102548 KB |
#include <bits/stdc++.h>
/*
Porque tú eres lo que necesito
Porque yo soy lo que tú necesitas
Que tu cuerpo es mi lugar favorito
Y tu boca mi comida favorita
Tú eres perfecta, sin el 90-60-90
Después de al mundo yo darle la vuelta
Te tenía al lado y no me había dado cuenta
Que tú eres perfecta
Quiero que exageres como yo exagero
Y no te me reías porque esto es en serio
*/
#define debug printf
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long
const int MAXN = 2e5+10 ;
const ll inf = 1e15 ;
using namespace std ;
struct PersistentSeg
{
vector<int> sumQtd , lef, rig ;
vector<ll> sumValues ;
PersistentSeg()
{
sumValues.resize(1,0LL) ;
sumQtd.resize(1,0) ;
lef.resize(1,0) ;
rig.resize(1,0) ;
}
int create( int pos )
{
sumValues.push_back( sumValues[pos] ) ;
sumQtd.push_back( sumQtd[pos] ) ;
lef.push_back(lef[pos] ) ;
rig.push_back(rig[pos] ) ;
return sz(lef)-1 ;
}
int mid(int l, int r ) { return (l+r)>>1 ; }
int upd(int pos, int l , int r, int x, ll val )
{
int newPos = create(pos) , aux ;
sumValues[newPos] += val ;
sumQtd[newPos]++ ;
if( l == r ) return newPos ;
if( x <= mid(l,r) )
{
aux = upd(lef[newPos], l, mid(l,r) , x , val ) ;
lef[newPos] = aux ;
}
else
{
aux = upd(rig[newPos], mid(l,r)+1, r, x, val ) ;
rig[newPos] = aux ;
}
return newPos ;
}
ll bb(int posL, int posR, int l, int r , int &m ) //returns the sum of the M bests
{
if( m <= 0 ) return 0LL ;
if( sumQtd[posR]-sumQtd[posL] <= m )
{
m -= sumQtd[posR]-sumQtd[posL] ;
return sumValues[posR]-sumValues[posL] ;
}
ll ar = bb(rig[posL], rig[posR] , mid(l,r)+1, r, m ) ;
ll al = 0LL ;
if( m ) al = bb(lef[posL], lef[posR], l , mid(l,r), m ) ;
return al + ar ;
}
} seg ;
int n , m ;
int roots[MAXN] ;
pair<int,int> pieces[MAXN] ;
vector< pair<int,int> > compression ;
ll bestAnswer = -inf ;
ll getCost(int l, int r )
{
if(r-l+1 < m ) return -inf ;
int fuel = m ;
ll sumV = -2LL*(pieces[r].first - pieces[l].first );
sumV += seg.bb(roots[l-1], roots[r], 1, n, fuel ) ;
return sumV ;
}
void solve(int l, int r, int optmin, int optmax )
{
if( l > r ) return ;
int mid = (l+r)>>1 ;
int opt = mid ;
ll valOpt = -inf ;
for(int i = max(optmin, mid) ; i <= optmax ; i++ )
{
ll cost = getCost(mid,i) ;
if( cost <= valOpt ) continue ;
valOpt = cost ;
opt = i ;
}
if(bestAnswer < valOpt ) bestAnswer = valOpt ;
solve(l, mid-1, optmin, opt ) ;
solve(mid+1, r, opt, optmax ) ;
}
int main()
{
scanf("%d %d", &n, &m ) ;
for(int i = 1 ; i <= n ; i++ )
scanf("%d %d", &pieces[i].second, &pieces[i].first ) ;
//I need all of them to be different for simplicity's sake
//Will this mess things up?
sort(pieces+1, pieces+1+n) ;
for(int i = 1 ; i <= n ; i++ ) compression.push_back(make_pair(pieces[i].second,i) ) ;
sort(all(compression) ) ;
for(int i = 1 ; i <= n ; i++ )
{
int idx = lower_bound(all(compression), make_pair(pieces[i].second, i) ) - compression.begin() + 1 ;
roots[i] = seg.upd(roots[i-1], 1 , n , idx , (ll)pieces[i].second ) ;
}
solve(1,n-m+1, 1, n) ;
printf("%lld\n", bestAnswer ) ;
}
Compilation message
cake3.cpp: In function 'int main()':
cake3.cpp:147:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
147 | scanf("%d %d", &n, &m ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~
cake3.cpp:149:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
149 | scanf("%d %d", &pieces[i].second, &pieces[i].first ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
364 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
364 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
38 |
Correct |
4 ms |
1004 KB |
Output is correct |
39 |
Correct |
4 ms |
1128 KB |
Output is correct |
40 |
Correct |
4 ms |
1128 KB |
Output is correct |
41 |
Correct |
3 ms |
1004 KB |
Output is correct |
42 |
Correct |
3 ms |
1128 KB |
Output is correct |
43 |
Correct |
3 ms |
1004 KB |
Output is correct |
44 |
Correct |
4 ms |
1004 KB |
Output is correct |
45 |
Correct |
4 ms |
1128 KB |
Output is correct |
46 |
Correct |
4 ms |
1128 KB |
Output is correct |
47 |
Correct |
4 ms |
1004 KB |
Output is correct |
48 |
Correct |
4 ms |
1004 KB |
Output is correct |
49 |
Correct |
4 ms |
1128 KB |
Output is correct |
50 |
Correct |
4 ms |
1128 KB |
Output is correct |
51 |
Correct |
4 ms |
1128 KB |
Output is correct |
52 |
Correct |
3 ms |
1004 KB |
Output is correct |
53 |
Correct |
4 ms |
1004 KB |
Output is correct |
54 |
Correct |
3 ms |
1128 KB |
Output is correct |
55 |
Correct |
3 ms |
1004 KB |
Output is correct |
56 |
Correct |
3 ms |
1004 KB |
Output is correct |
57 |
Correct |
3 ms |
1004 KB |
Output is correct |
58 |
Correct |
3 ms |
1004 KB |
Output is correct |
59 |
Correct |
3 ms |
1004 KB |
Output is correct |
60 |
Correct |
4 ms |
1004 KB |
Output is correct |
61 |
Correct |
3 ms |
1004 KB |
Output is correct |
62 |
Correct |
3 ms |
1128 KB |
Output is correct |
63 |
Correct |
4 ms |
1128 KB |
Output is correct |
64 |
Correct |
5 ms |
1128 KB |
Output is correct |
65 |
Correct |
4 ms |
1132 KB |
Output is correct |
66 |
Correct |
4 ms |
1004 KB |
Output is correct |
67 |
Correct |
4 ms |
1128 KB |
Output is correct |
68 |
Correct |
4 ms |
1128 KB |
Output is correct |
69 |
Correct |
4 ms |
1004 KB |
Output is correct |
70 |
Correct |
4 ms |
1128 KB |
Output is correct |
71 |
Correct |
3 ms |
1004 KB |
Output is correct |
72 |
Correct |
3 ms |
1128 KB |
Output is correct |
73 |
Correct |
4 ms |
1004 KB |
Output is correct |
74 |
Correct |
3 ms |
1128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
364 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
364 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
1 ms |
364 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
1 ms |
364 KB |
Output is correct |
10 |
Correct |
1 ms |
364 KB |
Output is correct |
11 |
Correct |
1 ms |
364 KB |
Output is correct |
12 |
Correct |
1 ms |
364 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Correct |
1 ms |
364 KB |
Output is correct |
15 |
Correct |
1 ms |
364 KB |
Output is correct |
16 |
Correct |
1 ms |
364 KB |
Output is correct |
17 |
Correct |
1 ms |
364 KB |
Output is correct |
18 |
Correct |
1 ms |
364 KB |
Output is correct |
19 |
Correct |
1 ms |
364 KB |
Output is correct |
20 |
Correct |
1 ms |
364 KB |
Output is correct |
21 |
Correct |
1 ms |
364 KB |
Output is correct |
22 |
Correct |
1 ms |
364 KB |
Output is correct |
23 |
Correct |
1 ms |
364 KB |
Output is correct |
24 |
Correct |
1 ms |
364 KB |
Output is correct |
25 |
Correct |
1 ms |
364 KB |
Output is correct |
26 |
Correct |
1 ms |
364 KB |
Output is correct |
27 |
Correct |
1 ms |
364 KB |
Output is correct |
28 |
Correct |
1 ms |
364 KB |
Output is correct |
29 |
Correct |
1 ms |
364 KB |
Output is correct |
30 |
Correct |
1 ms |
364 KB |
Output is correct |
31 |
Correct |
1 ms |
364 KB |
Output is correct |
32 |
Correct |
1 ms |
364 KB |
Output is correct |
33 |
Correct |
1 ms |
364 KB |
Output is correct |
34 |
Correct |
1 ms |
364 KB |
Output is correct |
35 |
Correct |
1 ms |
364 KB |
Output is correct |
36 |
Correct |
1 ms |
364 KB |
Output is correct |
37 |
Correct |
1 ms |
364 KB |
Output is correct |
38 |
Correct |
4 ms |
1004 KB |
Output is correct |
39 |
Correct |
4 ms |
1128 KB |
Output is correct |
40 |
Correct |
4 ms |
1128 KB |
Output is correct |
41 |
Correct |
3 ms |
1004 KB |
Output is correct |
42 |
Correct |
3 ms |
1128 KB |
Output is correct |
43 |
Correct |
3 ms |
1004 KB |
Output is correct |
44 |
Correct |
4 ms |
1004 KB |
Output is correct |
45 |
Correct |
4 ms |
1128 KB |
Output is correct |
46 |
Correct |
4 ms |
1128 KB |
Output is correct |
47 |
Correct |
4 ms |
1004 KB |
Output is correct |
48 |
Correct |
4 ms |
1004 KB |
Output is correct |
49 |
Correct |
4 ms |
1128 KB |
Output is correct |
50 |
Correct |
4 ms |
1128 KB |
Output is correct |
51 |
Correct |
4 ms |
1128 KB |
Output is correct |
52 |
Correct |
3 ms |
1004 KB |
Output is correct |
53 |
Correct |
4 ms |
1004 KB |
Output is correct |
54 |
Correct |
3 ms |
1128 KB |
Output is correct |
55 |
Correct |
3 ms |
1004 KB |
Output is correct |
56 |
Correct |
3 ms |
1004 KB |
Output is correct |
57 |
Correct |
3 ms |
1004 KB |
Output is correct |
58 |
Correct |
3 ms |
1004 KB |
Output is correct |
59 |
Correct |
3 ms |
1004 KB |
Output is correct |
60 |
Correct |
4 ms |
1004 KB |
Output is correct |
61 |
Correct |
3 ms |
1004 KB |
Output is correct |
62 |
Correct |
3 ms |
1128 KB |
Output is correct |
63 |
Correct |
4 ms |
1128 KB |
Output is correct |
64 |
Correct |
5 ms |
1128 KB |
Output is correct |
65 |
Correct |
4 ms |
1132 KB |
Output is correct |
66 |
Correct |
4 ms |
1004 KB |
Output is correct |
67 |
Correct |
4 ms |
1128 KB |
Output is correct |
68 |
Correct |
4 ms |
1128 KB |
Output is correct |
69 |
Correct |
4 ms |
1004 KB |
Output is correct |
70 |
Correct |
4 ms |
1128 KB |
Output is correct |
71 |
Correct |
3 ms |
1004 KB |
Output is correct |
72 |
Correct |
3 ms |
1128 KB |
Output is correct |
73 |
Correct |
4 ms |
1004 KB |
Output is correct |
74 |
Correct |
3 ms |
1128 KB |
Output is correct |
75 |
Correct |
973 ms |
94612 KB |
Output is correct |
76 |
Correct |
1016 ms |
96040 KB |
Output is correct |
77 |
Correct |
926 ms |
97904 KB |
Output is correct |
78 |
Correct |
946 ms |
98836 KB |
Output is correct |
79 |
Correct |
379 ms |
99220 KB |
Output is correct |
80 |
Correct |
434 ms |
97304 KB |
Output is correct |
81 |
Correct |
920 ms |
97684 KB |
Output is correct |
82 |
Correct |
1064 ms |
98580 KB |
Output is correct |
83 |
Correct |
1033 ms |
100884 KB |
Output is correct |
84 |
Correct |
1044 ms |
100628 KB |
Output is correct |
85 |
Correct |
935 ms |
98360 KB |
Output is correct |
86 |
Correct |
581 ms |
96148 KB |
Output is correct |
87 |
Correct |
607 ms |
95380 KB |
Output is correct |
88 |
Correct |
830 ms |
94740 KB |
Output is correct |
89 |
Correct |
796 ms |
98412 KB |
Output is correct |
90 |
Correct |
619 ms |
101424 KB |
Output is correct |
91 |
Correct |
474 ms |
96148 KB |
Output is correct |
92 |
Correct |
484 ms |
95636 KB |
Output is correct |
93 |
Correct |
534 ms |
98472 KB |
Output is correct |
94 |
Correct |
457 ms |
101140 KB |
Output is correct |
95 |
Correct |
602 ms |
101396 KB |
Output is correct |
96 |
Correct |
447 ms |
96404 KB |
Output is correct |
97 |
Correct |
462 ms |
101396 KB |
Output is correct |
98 |
Correct |
471 ms |
100500 KB |
Output is correct |
99 |
Correct |
440 ms |
100628 KB |
Output is correct |
100 |
Correct |
395 ms |
96660 KB |
Output is correct |
101 |
Correct |
402 ms |
96792 KB |
Output is correct |
102 |
Correct |
861 ms |
96788 KB |
Output is correct |
103 |
Correct |
821 ms |
95892 KB |
Output is correct |
104 |
Correct |
901 ms |
99348 KB |
Output is correct |
105 |
Correct |
789 ms |
99092 KB |
Output is correct |
106 |
Correct |
788 ms |
100756 KB |
Output is correct |
107 |
Correct |
642 ms |
98604 KB |
Output is correct |
108 |
Correct |
886 ms |
98452 KB |
Output is correct |
109 |
Correct |
803 ms |
102548 KB |
Output is correct |
110 |
Correct |
425 ms |
96532 KB |
Output is correct |
111 |
Correct |
529 ms |
97300 KB |
Output is correct |
112 |
Correct |
693 ms |
94356 KB |
Output is correct |
113 |
Correct |
392 ms |
102548 KB |
Output is correct |