This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <fstream>
#include <climits>
#include <algorithm>
using namespace std;
const int nmax=200005;
pair<int,int> v[nmax],nrm[nmax];
pair<int,long long> aib[nmax];
long long glob=LLONG_MIN;
int act[nmax];
int n,i,j,k;
inline int lbit(int x)
{
return (((x^(x-1))&x));
}
void update(int poz,int v1,long long v2)
{
for(int idx=poz;idx<=n;idx+=lbit(idx))
aib[idx].first+=v1,aib[idx].second+=v2;
}
long long best_k(int k)
{
int ret=0,poz=0;
long long sum=0;
for(int p=17;p>=0;p--)
if(poz+(1<<p)<=n&&ret+aib[poz+(1<<p)].first<=k)
{
poz+=(1<<p);
ret+=aib[poz].first;
sum+=aib[poz].second;
}
return sum;
}
int ap[nmax];
void baga(int poz)
{
ap[poz]++;
update(act[poz],1,v[poz].second);
}
void scoate(int poz)
{
ap[poz]--;
update(act[poz],-1,-v[poz].second);
}
long long get_cost(int l,int r)
{
if(r-l+1<k) return LLONG_MIN;
return -2LL*(v[r].first-v[l].first)+1LL*best_k(k);
}
void divide(int st,int dr,int optst,int optdr)
{
int m=(st+dr)/2,opt=0;
long long val,mx=LLONG_MIN;
if(st>dr) return;
//ne asiguram ca e bagat tot intervalul [optdr,st-1] inainte de asta
for(int i=max(st,optdr);i<=m;i++)
baga(i);
val=get_cost(optdr,m);
if(val>mx)
mx=val,opt=optdr;
if(val>glob)
glob=val;
for(int i=min(optdr,m);i>=st;i--)
{
val=get_cost(i,m);
if(val>mx)
mx=val,opt=i;
if(val>glob)
glob=val;
}
for(int i=min(optdr-1,st-1);i>=optst;i--)
{
baga(i);
val=get_cost(i,m);
if(val>mx)
mx=val,opt=i;
if(val>glob)
glob=val;
}
if(!opt) opt=optst;
//acum e bagat tot [optst;m]
for(int i=optst;i<=min(optdr-1,m);i++)
scoate(i);
//acum e bagat [optdr;m]
divide(m+1,dr,opt,optdr);
for(int i=opt;i<optdr;i++)
baga(i);
//acum e bagat [opt;m]
for(int i=st;i<=m;i++)
scoate(i);
//acum e bagat[opt;st-1]
divide(st,m-1,optst,opt);
for(int i=opt;i<=min(optdr-1,st-1);i++)
scoate(i);
}
int main()
{
// freopen("data.in","r",stdin);
ios_base::sync_with_stdio(false);
cin>>n>>k;
for(i=1;i<=n;i++)
{
cin>>v[i].second>>v[i].first;
}
sort(v+1,v+n+1);
for(i=1;i<=n;i++)
{
nrm[i].first=v[i].second;
nrm[i].second=i;
}
sort(nrm+1,nrm+n+1);
reverse(nrm+1,nrm+n+1);
for(i=1;i<=n;i++)
act[nrm[i].second]=i;
divide(k,n,1,n-k+1);
cout<<glob;
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... |