Submission #487935

#	Time	Username	Problem	Language	Result	Execution time	Memory
487935		ToroTN	Salesman (IOI09_salesman)	C++14	60 / 100	768 ms	33480 KiB

salesman

#include<bits/stdc++.h>
using namespace std;
long long n,d,u,s,l[500005],m[500005],t_i,l_i,m_i,seg1[2000005],seg2[2000005],num1,num2;
void build(long long tree,long long st,long long ed)
{
    int md=(st+ed)/2;
    if(st==ed)
    {
        if(st<=s)
        {
            seg1[tree]=u*(500002-s);
        }else
        {
            seg1[tree]=-1e18;
        }
        if(st>=s)
        {
            seg2[tree]=d*s;
        }else
        {
            seg2[tree]=-1e18;
        }
        return;
    }
    build(2*tree,st,md);
    build(2*tree+1,md+1,ed);
    seg1[tree]=max(seg1[2*tree],seg1[2*tree+1]);
    seg2[tree]=max(seg2[2*tree],seg2[2*tree+1]);
}
void update1(long long tree,long long st,long long ed,long long idx,long long val)
{
    long long md=(st+ed)/2;
    if(st==ed)
    {
        seg1[tree]=max(seg1[tree],val);
        return;
    }
    if(idx<=md)
    {
        update1(2*tree,st,md,idx,val);
    }else
    {
        update1(2*tree+1,md+1,ed,idx,val);
    }
    seg1[tree]=max(seg1[2*tree],seg1[2*tree+1]);
}
void update2(long long tree,long long st,long long ed,long long idx,long long val)
{
    long long md=(st+ed)/2;
    if(st==ed)
    {
        seg2[tree]=max(seg2[tree],val);
        return;
    }
    if(idx<=md)
    {
        update2(2*tree,st,md,idx,val);
    }else
    {
        update2(2*tree+1,md+1,ed,idx,val);
    }
    seg2[tree]=max(seg2[2*tree],seg2[2*tree+1]);
}
long long query1(long long tree,long long st,long long ed,long long l,long long r)
{
    long long md=(st+ed)/2;
    if(st>r||ed<l)
    {
        return -1e18;
    }
    if(st>=l&&ed<=r)
    {
        return seg1[tree];
    }
    return max(query1(2*tree,st,md,l,r),query1(2*tree+1,md+1,ed,l,r));
}
long long query2(long long tree,long long st,long long ed,long long l,long long r)
{
    long long md=(st+ed)/2;
    if(st>r||ed<l)
    {
        return -1e18;
    }
    if(st>=l&&ed<=r)
    {
        return seg2[tree];
    }
    return max(query2(2*tree,st,md,l,r),query2(2*tree+1,md+1,ed,l,r));
}
void debug(long long tree,long long st,long long ed)
{
    long long md=(st+ed)/2;
    if(st==ed)
    {
        printf("%lld %lld %lld\n",st,seg1[tree],seg2[tree]);
        return;
    }
    debug(2*tree,st,md);
    debug(2*tree+1,md+1,ed);
}
int main()
{
    scanf("%lld%lld%lld%lld",&n,&u,&d,&s);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",&t_i,&l_i,&m_i);
        l[t_i]=l_i;
        m[t_i]=m_i;
    }
    build(1,1,500001);
    //printf("%lld\n",max(query2(1,1,500001,1,s)-d*s,query1(1,1,500001,s,500001)-u*(500002-s)));
    for(int i=1;i<=500000;i++)
    {
        if(l[i]!=0&&m[i]!=0)
        {
            //printf("%d %lld %lld\n",i,l[i],m[i]);
            num1=query1(1,1,500001,l[i],500001);
            num2=query2(1,1,500001,1,l[i]);
            update1(1,1,500001,l[i],m[i]+num1);
            update1(1,1,500001,l[i],m[i]+num2-d*l[i]+u*(500002-l[i]));
            update2(1,1,500001,l[i],m[i]+num2);
            update2(1,1,500001,l[i],m[i]+num1-u*(500002-l[i])+d*l[i]);
            //debug(1,1,500001);
            //printf("%lld\n",max(query2(1,1,500001,1,s)-d*s,query1(1,1,500001,s,500001)-u*(500002-s)));
        }
    }
    printf("%lld\n",max(query2(1,1,500001,1,s)-d*s,query1(1,1,500001,s,500001)-u*(500002-s)));
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:103:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |     scanf("%lld%lld%lld%lld",&n,&u,&d,&s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         scanf("%lld%lld%lld",&t_i,&l_i,&m_i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100