oj.uz

Submission #617958

# Submission time Handle Problem Language Result Execution time Memory
617958 2022-08-01T18:01:38 Z Bench0310 Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 212 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB n = 4, 80 is a correct answer
2 Correct 1 ms 212 KB n = 9, 110 is a correct answer
3 Correct 0 ms 212 KB n = 4, 21 is a correct answer
4 Correct 1 ms 212 KB n = 3, 4 is a correct answer
5 Incorrect 0 ms 212 KB n = 2, incorrect answer: jury 62 vs contestant 72
6 Halted 0 ms 0 KB -