Submission #407114

#	Time	Username	Problem	Language	Result	Execution time	Memory
407114		MKopchev	Shortcut (IOI16_shortcut)	C++14	97 / 100	2091 ms	44940 KiB

shortcut

#include "shortcut.h"
#include<bits/stdc++.h>
using namespace std;

const long long inf=1e18;

vector<long long> x={},add={};

int cut;

vector<int> order_j,order_i;

bool cmp_i(int a,int b)
{
    return x[a]-add[a]<x[b]-add[b];
}

bool cmp_j(int a,int b)
{
    return x[a]+add[a]<x[b]+add[b];
}
bool test(long long sz)
{
    pair<long long,int> sum_low_help[2]={{-inf,-1},{-inf,-1}};
    pair<long long,int> diff_low_help[2]={{-inf,-1},{-inf,-1}};

    pair<long long,int> sum_high_help[2]={{inf,-1},{inf,-1}};
    pair<long long,int> diff_high_help[2]={{inf,-1},{inf,-1}};

    long long sum_low=-inf,sum_high=inf;

    long long diff_low=-inf,diff_high=inf;

    int id_i=0;

    for(auto j:order_j)
    {
        while(id_i<x.size())
        {
            int i=order_i[id_i];

            if(add[j]+x[j]-(x[i]-add[i])>sz)
            {
                pair<long long,int> me={add[i]+x[i],i};
                if(sum_low_help[0].first<=me.first)
                {
                    sum_low_help[1]=sum_low_help[0];
                    sum_low_help[0]=me;
                }
                else if(sum_low_help[1].first<=me.first)sum_low_help[1]=me;



                me={add[i]-x[i],i};
                if(diff_low_help[0].first<=me.first)
                {
                    diff_low_help[1]=diff_low_help[0];
                    diff_low_help[0]=me;
                }
                else if(diff_low_help[1].first<=me.first)diff_low_help[1]=me;



                me={x[i]-add[i],i};
                if(sum_high_help[0].first>=me.first)
                {
                    sum_high_help[1]=sum_high_help[0];
                    sum_high_help[0]=me;
                }
                else if(sum_high_help[1].first>=me.first)sum_high_help[1]=me;




                me={-x[i]-add[i],i};
                if(diff_high_help[0].first>=me.first)
                {
                    diff_high_help[1]=diff_high_help[0];
                    diff_high_help[0]=me;
                }
                else if(diff_high_help[1].first>=me.first)diff_high_help[1]=me;


                id_i++;
            }
            else break;
        }

        for(int w=0;w<2;w++)
        {
            if(sum_low_help[w].second!=j)sum_low=max(sum_low,x[j]+add[j]+cut-sz+sum_low_help[w].first);

            if(diff_low_help[w].second!=j)diff_low=max(diff_low,x[j]+add[j]+cut-sz+diff_low_help[w].first);

            if(sum_high_help[w].second!=j)sum_high=min(sum_high,x[j]-add[j]-cut+sz+sum_high_help[w].first);

            if(diff_high_help[w].second!=j)diff_high=min(diff_high,x[j]-add[j]-cut+sz+diff_high_help[w].first);
        }

    }
    /*
    for(int i=0;i<x.size();i++)
        for(int j=i+1;j<x.size();j++)
            if(add[i]+x[j]-x[i]+add[j]<=sz)continue;
            else
            {
                //cout<<"wrong "<<i<<" "<<j<<endl;

                long long RHS=sz-add[i]-add[j]-cut;

                //cout<<"sz= "<<sz<<" RHS= "<<RHS<<endl;

                if(RHS<0)return 0;

                sum_low=max(sum_low,x[i]+x[j]-RHS);

                sum_high=min(sum_high,x[i]+x[j]+RHS);

                diff_low=max(diff_low,-x[i]+x[j]-RHS);

                diff_high=min(diff_high,-x[i]+x[j]+RHS);
            }
    */

    //cout<<"sz= "<<sz<<endl;

    //cout<<"sum: "<<sum_low<<" "<<sum_high<<" diff: "<<diff_low<<" "<<diff_high<<endl;

    if(sum_low>sum_high)return 0;

    if(diff_low>diff_high)return 0;

    int LHS_low=x.size(),LHS_high=x.size()-1;

    int RHS_low=0,RHS_high=-1;

    for(int frst=0;frst<x.size();frst++)
    {
        while(LHS_low&&sum_low-x[frst]<=x[LHS_low-1])LHS_low--;
        while(LHS_high>=0&&sum_high-x[frst]<x[LHS_high])LHS_high--;

        while(RHS_low<x.size()&&diff_low+x[frst]>x[RHS_low])RHS_low++;
        while(RHS_high+1<x.size()&&diff_high+x[frst]>=x[RHS_high+1])RHS_high++;

        //LHS_low<=pos<=LHS_high
        //RHS_low<=pos<=RHS_high

        int p=max(LHS_low,RHS_low);
        int q=min(LHS_high,RHS_high);

        p=max(p,frst+1);

        //cout<<"frst= "<<frst<<" "<<LHS_low<<" "<<LHS_high<<" "<<RHS_low<<" "<<RHS_high<<endl;

        if(p<=q)
        {
            //cout<<"sz= "<<sz<<" frst= "<<frst<<" p= "<<p<<" q= "<<q<<endl;

            return 1;
        }
    }

    return 0;
}
long long find_shortcut(int n, std::vector<int> l, std::vector<int> d, int c)
{
    long long sum=0;

    x.push_back(0);

    for(auto w:l)
    {
        sum+=w;
        x.push_back(sum);
    }

    for(auto w:d)
        add.push_back(w);

    for(int i=0;i<x.size();i++)
    {
        order_j.push_back(i);
        order_i.push_back(i);
    }

    sort(order_i.begin(),order_i.end(),cmp_i);
    sort(order_j.begin(),order_j.end(),cmp_j);


    cut=c;

    long long ok=2e9+x.back();
    long long not_ok=-1;

    while(ok-not_ok>1)
    {
        long long av=(ok+not_ok)/2;

        if(test(av))ok=av;
        else not_ok=av;
    }

    return ok;
}
/*
int main()
{
    int n, c;
    assert(2 == scanf("%d%d", &n, &c));

    std::vector<int> l(n - 1);
    std::vector<int> d(n);
    for (int i = 0; i < n - 1; i++)
        assert(1 == scanf("%d", &l[i]));
    for (int i = 0; i < n; i++)
        assert(1 == scanf("%d", &d[i]));

    long long t = find_shortcut(n, l, d, c);


    printf("%lld\n", t);

    return 0;
}
*/

Compilation message (stderr)

shortcut.cpp: In function 'bool test(long long int)':
shortcut.cpp:38:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         while(id_i<x.size())
      |               ~~~~^~~~~~~~~
shortcut.cpp:137:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     for(int frst=0;frst<x.size();frst++)
      |                    ~~~~^~~~~~~~~
shortcut.cpp:142:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |         while(RHS_low<x.size()&&diff_low+x[frst]>x[RHS_low])RHS_low++;
      |               ~~~~~~~^~~~~~~~~
shortcut.cpp:143:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |         while(RHS_high+1<x.size()&&diff_high+x[frst]>=x[RHS_high+1])RHS_high++;
      |               ~~~~~~~~~~^~~~~~~~~
shortcut.cpp: In function 'long long int find_shortcut(int, std::vector<int>, std::vector<int>, int)':
shortcut.cpp:180:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  180 |     for(int i=0;i<x.size();i++)
      |                 ~^~~~~~~~~

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