Submission #617958

#	Time	Username	Problem	Language	Result	Execution time	Memory
617958		Bench0310	Shortcut (IOI16_shortcut)	C++17	0 / 100	1 ms	212 KiB

shortcut

#include <bits/stdc++.h>
#include "shortcut.h"

using namespace std;
typedef long long ll;

struct ST
{
    int n;
    vector<ll> val;
    vector<array<ll,2>> tree;
    ST(vector<ll> &d)
    {
        n=d.size();
        val=d;
        tree.resize(4*n);
        build(1,0,n-1);
    }
    void build(int idx,int l,int r)
    {
        if(l==r) tree[idx]={val[l],l};
        else
        {
            int m=(l+r)/2;
            build(2*idx,l,m);
            build(2*idx+1,m+1,r);
            tree[idx]=max(tree[2*idx],tree[2*idx+1]);
        }
    }
    void update(int idx,int l,int r,int pos,ll x)
    {
        if(l==r) tree[idx][0]=x;
        else
        {
            int m=(l+r)/2;
            if(pos<=m) update(2*idx,l,m,pos,x);
            else update(2*idx+1,m+1,r,pos,x);
            tree[idx]=max(tree[2*idx],tree[2*idx+1]);
        }
    }
    void upd(int pos,ll x){update(1,0,n-1,pos,x);}
    array<ll,2> query(int idx,int l,int r,int ql,int qr)
    {
        if(ql>qr) return {-(1ll<<60),-1};
        if(l==ql&&r==qr) return tree[idx];
        int m=(l+r)/2;
        return max(query(2*idx,l,m,ql,min(qr,m)),query(2*idx+1,m+1,r,max(ql,m+1),qr));
    }
    array<ll,2> qry(int ql,int qr){return query(1,0,n-1,ql,qr);}
};

ll find_shortcut(int n,vector<int> len,vector<int> d,int c)
{
    vector<ll> lsum(n,0);
    for(int i=1;i<n;i++) lsum[i]=lsum[i-1]+len[i-1];
    vector<ll> rsum(n,0);
    for(int i=n-2;i>=0;i--) rsum[i]=rsum[i+1]+len[i];
    auto sum=[&](int l,int r)->ll{return (lsum[r]-lsum[l]);};
    vector<ll> dl(n,0);
    vector<ll> mxl(n,0);
    for(int i=0;i<n;i++)
    {
        dl[i]=max((i>0?dl[i-1]+len[i-1]:ll(0)),ll(d[i]));
        mxl[i]=max((i>0?mxl[i-1]:ll(0)),dl[i]+d[i]);
    }
    vector<ll> dr(n,0);
    vector<ll> mxr(n,0);
    for(int i=n-1;i>=0;i--)
    {
        dr[i]=max((i<n-1?dr[i+1]+len[i]:ll(0)),ll(d[i]));
        mxr[i]=max((i<n-1?mxr[i+1]:ll(0)),dr[i]+d[i]);
    }
    vector<ll> tmpl(n,0);
    for(int i=0;i<n;i++) tmpl[i]=rsum[i]+d[i];
    vector<ll> tmpr(n,0);
    for(int i=0;i<n;i++) tmpr[i]=lsum[i]+d[i];
    ST gol(tmpl);
    ST gor(tmpr);
    auto C=[&](int l,int r)->ll
    {
        ll diam=max(mxl[l],mxr[r]);
        ll cycle=sum(l,r)+c;
        gol.upd(l,rsum[l]+dl[l]);
        gor.upd(l,lsum[l]+dl[l]);
        gol.upd(r,rsum[r]+dr[r]);
        gor.upd(r,lsum[r]+dr[r]);
        auto getd=[&](int i)->ll
        {
            if(i==l) return dl[i];
            if(i==r) return dr[i];
            return d[i];
        };
        auto opt=[&](int p)->array<ll,2>
        {
            array<ll,2> tmp={-1,-1};
            //left
            int tl=l-1,tr=p;
            while(tl<tr-1)
            {
                int m=(tl+tr)/2;
                if(sum(m,p)<=cycle/2) tr=m;
                else tl=m;
            }
            auto [d1,i1]=gol.qry(tr,p);
            tmp=max(tmp,{d1-rsum[p]+getd(p),i1});
            auto [d2,i2]=gor.qry(l,tl);
            tmp=max(tmp,{d2-lsum[l]+sum(p,r)+c+getd(p),i2});
            //right
            tl=p,tr=r+1;
            while(tl<tr-1)
            {
                int m=(tl+tr)/2;
                if(sum(p,m)<=cycle/2) tl=m;
                else tr=m;
            }
            auto [d3,i3]=gor.qry(p,tl);
            tmp=max(tmp,{d3-lsum[p]+getd(p),i3});
            auto [d4,i4]=gol.qry(tr,r);
            tmp=max(tmp,{d4-rsum[r]+sum(l,p)+c+getd(p),i4});
            return tmp;
        };
        diam=max(diam,opt(opt(l)[1])[0]);
        gol.upd(l,rsum[l]+d[l]);
        gor.upd(l,lsum[l]+d[l]);
        gol.upd(r,rsum[r]+d[r]);
        gor.upd(r,lsum[r]+d[r]);
        return diam;
    };
    ll res=(1ll<<60);
    for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) res=min(res,C(i,j));
    return res;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3