이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
struct PST
{
int l, r, c;
long long s;
PST() : l(0), r(0), c(0), s(0) {}
};
const int SZ=1<<18;
int N, M, node_cnt;
pair<int,int> C[200000], x[200000];
PST tree[5555555];
long long ans;
void set_tree(int b, int n, int v, int p, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
if(s==e) {
tree[p].s=v;
tree[p].c=1;
return;
}
if(n<=m) {
tree[p].l=node_cnt++;
tree[p].r=tree[b].r;
set_tree(tree[b].l,n,v,tree[p].l,s,m);
}
else {
tree[p].r=node_cnt++;
tree[p].l=tree[b].l;
set_tree(tree[b].r,n,v,tree[p].r,m+1,e);
}
tree[p].s=tree[tree[p].l].s+tree[tree[p].r].s;
tree[p].c=tree[tree[p].l].c+tree[tree[p].r].c;
}
int kth(int l, int r, int k)
{
int s=0, e=SZ-1;
while(s<e) {
int m=(s+e)>>1;
if(tree[tree[r].l].c-tree[tree[l].l].c>=k) {
l=tree[l].l;
r=tree[r].l;
e=m;
}
else {
k-=tree[tree[r].l].c-tree[tree[l].l].c;
l=tree[l].r;
r=tree[r].r;
s=m+1;
}
}
return s;
}
long long get_sum(int n1, int n2, int p, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
if(p==0 || n2<n1 || n2<s || e<n1) return 0;
if(n1<=s && e<=n2) return tree[p].s;
return get_sum(n1,n2,tree[p].l,s,m)+get_sum(n1,n2,tree[p].r,m+1,e);
}
void solve(int s1, int e1, int s2, int e2)
{
int m1=(s1+e1)>>1, m2=-1;
long long mx=-0x7fffffffffffffffLL, t;
if(s1>e1) return;
for(int i=max(s2,m1+M-1);i<=e2;i++) {
int k=kth(m1,i+1,M);
if((t=get_sum(0,k,i+1)-get_sum(0,k,m1)-2LL*(C[i].first-C[m1].first))>=mx) {
mx=t;
m2=i;
}
}
ans=max(ans,mx);
solve(s1,m1-1,s2,m2);
solve(m1+1,e1,m2,e2);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
cin>>N>>M; node_cnt=N+1;
for(int i=0;i<N;i++) cin>>C[i].second>>C[i].first;
sort(C,C+N);
for(int i=0;i<N;i++) x[i]={C[i].second,i};
sort(x,x+N);
for(int i=0;i<N;i++) C[x[i].second].second=i;
for(int i=0;i<N;i++) set_tree(i,N-C[i].second,x[C[i].second].first,i+1);
solve(0,N-M,M-1,N-1);
cout<<ans<<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |