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<bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
const ll maxn =2e5+10;
const ll mod=1e9+7;
const ll base=1e18;
ll st[4*maxn];
ll st1[4*maxn];
ll val[maxn];
ll pos[maxn];
pll a[maxn];
struct tk
{
ll n;
ll l=1;
ll r=0;
void update(ll id,ll left,ll right,ll x,ll diff)
{
if (x>right||x<left)
return ;
if (left==right)
{
st[id]+=diff;
st1[id]+=val[left]*diff;
return ;
}
ll mid=(left+right)/2;
update(id*2,left,mid, x, diff);
update(id*2+1,mid+1, right, x, diff);
st[id]=st[id*2]+st[id*2+1];
st1[id]=st1[id*2]+st1[id*2+1];
}
void finit(ll n1)
{
l=1;
r=0;
init(1,1,n1);
n=n1;
}
void init(ll id,ll left,ll right)
{
st[id]=0;
st1[id]=0;
if (left==right)
return ;
ll mid=(left+right)/2;
init(id*2,left,mid);
init(id*2+1,mid+1, right);
}
void ers(ll t)
{
update(1,1,n,t,-1);
}
void add(ll t)
{
update(1,1,n,t,1);
}
ll get1(ll lf,ll rt,ll x)
{
if (x<0) return -base;
while (l>lf)
{
l--;
add(pos[l]);
}
while (l<lf)
{
ers(pos[l]);
l++;
}
while (r<rt)
{
r++;
add(pos[r]);
}
while (r>rt)
{
ers(pos[r]);
r--;
}
if (x>st[1])
{
return st1[1];
}
return get(1,1,n,x);
}
ll get(ll id,ll left,ll right,ll x)
{
if (left==right)
{
return val[left]*x;
}
ll mid=(left+right)/2;
if (st[id*2+1]<x)
{
return get(id*2,left,mid,x-st[id*2+1])+st1[id*2+1];
}
else
{
return get(id*2+1,mid+1,right,x);
}
}
} man;
ll ans[maxn];
void dac(ll l,ll r,ll low,ll high,ll d)
{
if (l>r) return ;
ll mid=(l+r)/2;
ll pos_best=-1;
ans[mid]=-base;
for (int i=low;i<=min(mid,min(mid-d+1,high));i++)
{
ll t=man.get1(i,mid,d)-2*(a[mid].ff-a[i].ff);
if (ans[mid]<t)
{
ans[mid]=t;
pos_best=i;
}
}
dac(l,mid-1,low,pos_best,d);
dac(mid+1,r,pos_best,high,d);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
if (fopen("t.inp","r"))
{
freopen("test.inp","r",stdin);
freopen("test.out","w",stdout);
}
ll n,m;
cin>> n>> m;
vector<ll> vt;
for (int i=1;i<=n;i++)
{
cin>>a[i].ss>>a[i].ff;
vt.pb(a[i].ss);
}
sort(a+1,a+n+1);
sort(vt.begin(),vt.end());
vt.resize(unique(vt.begin(),vt.end())-vt.begin());
for (int i=1;i<=n;i++)
{
pos[i]=lower_bound(vt.begin(),vt.end(),a[i].ss)-vt.begin()+1;
}
ll siz=vt.size();
for (int i=1;i<=siz;i++)
{
val[i]=vt[i-1];
}
man.finit(siz);
dac(m,n,1,n,m);
ll res=0;
for (int i=1;i<=n;i++)
{
res=max(res,ans[i]);
}
cout <<res;
}
Compilation message (stderr)
cake3.cpp: In function 'int main()':
cake3.cpp:143:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
143 | freopen("test.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
144 | freopen("test.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |