Submission #362781

#	Time	Username	Problem	Language	Result	Execution time	Memory
362781		Dymo	Cake 3 (JOI19_cake3)	C++14	100 / 100	2856 ms	21984 KiB

cake3

#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;
   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);
    }
    /*5 5
2 1
4 2
6 4
8 8
10 120*/
    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);
    for (int i=1;i<=n;i++)
    {
        ans[i]=-base;
    }
    dac(m,n,1,n,m);
    ll res=-base;
    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:142:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  142 |         freopen("test.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76