//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#define endl '\n'
llo n,m;
llo ll[200000*30];
llo rr[200000*30];
llo tree[200000*30];
llo ll2[200000*30];
llo rr2[200000*30];
llo tree2[200000*30];
llo ind[200001];
vector<llo> rr3;
vector<llo> rr4;
llo co=0;
llo update(llo no,llo l,llo r,llo i){
llo cur=co;
co++;
ll[cur]=ll[no];
rr[cur]=rr[no];
tree[cur]=tree[no];
if(l==r){
tree[cur]+=1;
return cur;
}
else{
llo mid=(l+r)/2;
if(i<=mid){
ll[cur]=update(ll[no],l,mid,i);
}
else{
rr[cur]=update(rr[no],mid+1,r,i);
}
tree[cur]=tree[ll[cur]]+tree[rr[cur]];
return cur;
}
}
llo query(llo no,llo no2,llo l,llo r,llo k){
if(l==r){
return l;
}
else{
llo mid=(l+r)/2;
if(tree[ll[no2]]-tree[ll[no]]>=k){
return query(ll[no],ll[no2],l,mid,k);
}
else{
return query(rr[no],rr[no2],mid+1,r,k-(tree[ll[no2]]-tree[ll[no]]));
}
}
}
llo co2=0;
llo update2(llo no,llo l,llo r,llo i,llo val){
llo cur=co2;
co2++;
ll2[cur]=ll2[no];
rr2[cur]=rr2[no];
tree2[cur]=tree2[no];
if(l==r){
tree2[cur]+=val;
return cur;
}
else{
llo mid=(l+r)/2;
if(i<=mid){
ll2[cur]=update2(ll2[no],l,mid,i,val);
}
else{
rr2[cur]=update2(rr2[no],mid+1,r,i,val);
}
tree2[cur]=tree2[ll2[cur]]+tree2[rr2[cur]];
return cur;
}
}
llo query2(llo no,llo l,llo r,llo aa,llo bb){
if(r<aa or l>bb){
return 0;
}
if(aa<=l and r<=bb){
return tree2[no];
}
else{
llo mid=(l+r)/2;
return query2(ll2[no],l,mid,aa,bb)+query2(rr2[no],mid+1,r,aa,bb);
}
}
vector<pair<llo,llo>> ss;
vector<pair<llo,llo>> ee;
llo solve(llo l,llo r){
llo su=ss[l].b+ss[r].b-2*(ss[r].a-ss[l].a);
l++;
r--;
llo kk=query(rr3[l],rr3[r+1],0,n-1,m-2);
llo cot=query2(rr4[kk+1],0,n-1,l,r);//+su;
//cout<<l-1<<":"<<r+1<<":"<<cot<<endl;
//cout<<kk<<",,"<<endl;
return cot+su;
}
llo ans=-1e18;
void solve(int l,int r,int aa,int bb){
int mid=(l+r)/2;
pair<llo,llo> ma={-1e18,-1};
for(int i=max(aa,mid);i<=bb;i++){
if(i-mid+1>=m){
//cout<<mid<<":"<<i<<endl;
pair<llo,llo> cur={solve(mid,i),i};
if(cur.a>ma.a){
ma=cur;
}
}
}
// cout<<mid<<":"<<ma.b<<endl;
ans=max(ans,ma.a);
if(mid>l){
solve(l,mid-1,aa,ma.b);
}
if(mid<r){
solve(mid+1,r,ma.b,bb);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
for(llo i=0;i<2*n;i++){
ll[i]=2*i+1;
rr[i]=2*i+2;
ll2[i]=2*i+1;
rr2[i]=2*i+2;
co=max(co,rr[i]+1);
co2=max(co2,rr[i]+1);
}
for(llo i=0;i<n;i++){
llo aa,bb;
cin>>aa>>bb;
ss.pb({bb,aa});
}
sort(ss.begin(),ss.end());
/*for(auto j:ss){
cout<<j.a<<":"<<j.b<<endl;
}*/
for(llo i=0;i<n;i++){
ee.pb({-ss[i].b,i});
}
sort(ee.begin(),ee.end());
for(llo i=0;i<n;i++){
ind[ee[i].b]=i;
}
rr3.pb(0);
for(llo i=0;i<n;i++){
llo x=update(rr3.back(),0,n-1,ind[i]);
rr3.pb(x);
}
rr4.pb(0);
for(llo i=0;i<n;i++){
rr4.pb(update2(rr4.back(),0,n-1,ee[i].b,-ee[i].a));
}
solve(0,n-m,0,n-1);
cout<<ans<<endl;
return 0;
llo la=-1;
/* for(auto j:ss){
cout<<j.a<<"."<<j.b<<endl;
}*/
for(llo i=0;i<n;i++){
llo su=ss[i].b+2*ss[i].a;
priority_queue<llo> tt;
pair<llo,llo> ma={-1e18,-1};
for(llo j=i+1;j<n;j++){
while(tt.size()>m-2){
su+=tt.top();
tt.pop();
}
if(j>=la){
if(j-i-1>=m-2){
pair<llo,llo> cur={solve(i,j),j};
if(cur.a>ma.a){
ma=cur;
}
}
}
su+=ss[j].b;
tt.push(-ss[j].b);
}
ans=max(ans,ma.a);
la=ma.b;
}
cout<<ans<<endl;
return 0;
}
Compilation message
cake3.cpp: In function 'int main()':
cake3.cpp:188:19: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'llo' {aka 'long long int'} [-Wsign-compare]
188 | while(tt.size()>m-2){
| ~~~~~~~~~^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
336 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
336 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
336 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
336 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
6 ms |
1612 KB |
Output is correct |
39 |
Correct |
6 ms |
1740 KB |
Output is correct |
40 |
Correct |
4 ms |
1612 KB |
Output is correct |
41 |
Correct |
4 ms |
1612 KB |
Output is correct |
42 |
Correct |
4 ms |
1612 KB |
Output is correct |
43 |
Correct |
4 ms |
1612 KB |
Output is correct |
44 |
Correct |
5 ms |
1556 KB |
Output is correct |
45 |
Correct |
6 ms |
1632 KB |
Output is correct |
46 |
Correct |
6 ms |
1740 KB |
Output is correct |
47 |
Correct |
7 ms |
1612 KB |
Output is correct |
48 |
Correct |
6 ms |
1612 KB |
Output is correct |
49 |
Correct |
5 ms |
1740 KB |
Output is correct |
50 |
Correct |
5 ms |
1740 KB |
Output is correct |
51 |
Correct |
5 ms |
1740 KB |
Output is correct |
52 |
Correct |
4 ms |
1612 KB |
Output is correct |
53 |
Correct |
5 ms |
1612 KB |
Output is correct |
54 |
Correct |
4 ms |
1740 KB |
Output is correct |
55 |
Correct |
3 ms |
1612 KB |
Output is correct |
56 |
Correct |
3 ms |
1612 KB |
Output is correct |
57 |
Correct |
3 ms |
1612 KB |
Output is correct |
58 |
Correct |
3 ms |
1612 KB |
Output is correct |
59 |
Correct |
4 ms |
1612 KB |
Output is correct |
60 |
Correct |
5 ms |
1612 KB |
Output is correct |
61 |
Correct |
4 ms |
1720 KB |
Output is correct |
62 |
Correct |
4 ms |
1740 KB |
Output is correct |
63 |
Correct |
4 ms |
1740 KB |
Output is correct |
64 |
Correct |
4 ms |
1740 KB |
Output is correct |
65 |
Correct |
6 ms |
1612 KB |
Output is correct |
66 |
Correct |
8 ms |
1612 KB |
Output is correct |
67 |
Correct |
6 ms |
1740 KB |
Output is correct |
68 |
Correct |
5 ms |
1740 KB |
Output is correct |
69 |
Correct |
5 ms |
1712 KB |
Output is correct |
70 |
Correct |
5 ms |
1740 KB |
Output is correct |
71 |
Correct |
5 ms |
1612 KB |
Output is correct |
72 |
Correct |
3 ms |
1740 KB |
Output is correct |
73 |
Correct |
6 ms |
1612 KB |
Output is correct |
74 |
Correct |
3 ms |
1740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
336 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
1 ms |
332 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
336 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
6 ms |
1612 KB |
Output is correct |
39 |
Correct |
6 ms |
1740 KB |
Output is correct |
40 |
Correct |
4 ms |
1612 KB |
Output is correct |
41 |
Correct |
4 ms |
1612 KB |
Output is correct |
42 |
Correct |
4 ms |
1612 KB |
Output is correct |
43 |
Correct |
4 ms |
1612 KB |
Output is correct |
44 |
Correct |
5 ms |
1556 KB |
Output is correct |
45 |
Correct |
6 ms |
1632 KB |
Output is correct |
46 |
Correct |
6 ms |
1740 KB |
Output is correct |
47 |
Correct |
7 ms |
1612 KB |
Output is correct |
48 |
Correct |
6 ms |
1612 KB |
Output is correct |
49 |
Correct |
5 ms |
1740 KB |
Output is correct |
50 |
Correct |
5 ms |
1740 KB |
Output is correct |
51 |
Correct |
5 ms |
1740 KB |
Output is correct |
52 |
Correct |
4 ms |
1612 KB |
Output is correct |
53 |
Correct |
5 ms |
1612 KB |
Output is correct |
54 |
Correct |
4 ms |
1740 KB |
Output is correct |
55 |
Correct |
3 ms |
1612 KB |
Output is correct |
56 |
Correct |
3 ms |
1612 KB |
Output is correct |
57 |
Correct |
3 ms |
1612 KB |
Output is correct |
58 |
Correct |
3 ms |
1612 KB |
Output is correct |
59 |
Correct |
4 ms |
1612 KB |
Output is correct |
60 |
Correct |
5 ms |
1612 KB |
Output is correct |
61 |
Correct |
4 ms |
1720 KB |
Output is correct |
62 |
Correct |
4 ms |
1740 KB |
Output is correct |
63 |
Correct |
4 ms |
1740 KB |
Output is correct |
64 |
Correct |
4 ms |
1740 KB |
Output is correct |
65 |
Correct |
6 ms |
1612 KB |
Output is correct |
66 |
Correct |
8 ms |
1612 KB |
Output is correct |
67 |
Correct |
6 ms |
1740 KB |
Output is correct |
68 |
Correct |
5 ms |
1740 KB |
Output is correct |
69 |
Correct |
5 ms |
1712 KB |
Output is correct |
70 |
Correct |
5 ms |
1740 KB |
Output is correct |
71 |
Correct |
5 ms |
1612 KB |
Output is correct |
72 |
Correct |
3 ms |
1740 KB |
Output is correct |
73 |
Correct |
6 ms |
1612 KB |
Output is correct |
74 |
Correct |
3 ms |
1740 KB |
Output is correct |
75 |
Correct |
2297 ms |
186980 KB |
Output is correct |
76 |
Correct |
2449 ms |
185240 KB |
Output is correct |
77 |
Correct |
2015 ms |
191108 KB |
Output is correct |
78 |
Correct |
2096 ms |
194124 KB |
Output is correct |
79 |
Correct |
477 ms |
194768 KB |
Output is correct |
80 |
Correct |
631 ms |
188996 KB |
Output is correct |
81 |
Correct |
1991 ms |
192216 KB |
Output is correct |
82 |
Correct |
2580 ms |
194880 KB |
Output is correct |
83 |
Correct |
2343 ms |
201572 KB |
Output is correct |
84 |
Correct |
2343 ms |
200956 KB |
Output is correct |
85 |
Correct |
2069 ms |
193828 KB |
Output is correct |
86 |
Correct |
1040 ms |
187000 KB |
Output is correct |
87 |
Correct |
1141 ms |
184448 KB |
Output is correct |
88 |
Correct |
1772 ms |
183240 KB |
Output is correct |
89 |
Correct |
1661 ms |
193920 KB |
Output is correct |
90 |
Correct |
1114 ms |
203228 KB |
Output is correct |
91 |
Correct |
782 ms |
187436 KB |
Output is correct |
92 |
Correct |
814 ms |
185852 KB |
Output is correct |
93 |
Correct |
923 ms |
194096 KB |
Output is correct |
94 |
Correct |
732 ms |
203004 KB |
Output is correct |
95 |
Correct |
1073 ms |
203564 KB |
Output is correct |
96 |
Correct |
736 ms |
188332 KB |
Output is correct |
97 |
Correct |
774 ms |
203820 KB |
Output is correct |
98 |
Correct |
810 ms |
200776 KB |
Output is correct |
99 |
Correct |
754 ms |
201268 KB |
Output is correct |
100 |
Correct |
625 ms |
189204 KB |
Output is correct |
101 |
Correct |
643 ms |
189244 KB |
Output is correct |
102 |
Correct |
2079 ms |
189360 KB |
Output is correct |
103 |
Correct |
1976 ms |
186556 KB |
Output is correct |
104 |
Correct |
2197 ms |
197324 KB |
Output is correct |
105 |
Correct |
1790 ms |
196656 KB |
Output is correct |
106 |
Correct |
1754 ms |
201896 KB |
Output is correct |
107 |
Correct |
1425 ms |
194496 KB |
Output is correct |
108 |
Correct |
1972 ms |
193016 KB |
Output is correct |
109 |
Correct |
1647 ms |
205132 KB |
Output is correct |
110 |
Correct |
793 ms |
189992 KB |
Output is correct |
111 |
Correct |
1055 ms |
192172 KB |
Output is correct |
112 |
Correct |
1845 ms |
183160 KB |
Output is correct |
113 |
Correct |
497 ms |
205360 KB |
Output is correct |