Submission #487950

#	Time	Username	Problem	Language	Result	Execution time	Memory
487950		ToroTN	Salesman (IOI09_salesman)	C++14	60 / 100	1237 ms	44244 KiB

salesman

#include<bits/stdc++.h>
using namespace std;
long long n,d,u,s,l,m,t_i,l_i,m_i,seg1[2000005],seg2[2000005],num1[500005],num2[500005];
vector<pair<int,int> > v[500005];
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);
        v[t_i].push_back({l_i,m_i});
    }
    for(int i=1;i<=500000;i++)
    {
        sort(v[i].begin(),v[i].end());
    }
    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++)
    {
        for(int j=0;j<v[i].size();j++)
        {
            l=v[i][j].first;
            num1[j]=query1(1,1,500001,l,500001);
            num2[j]=query2(1,1,500001,1,l);
        }
        for(int j=v[i].size()-1;j>=0;j--)
        {
            //printf("%d %lld %lld\n",i,l[i],m[i]);
            m=v[i][j].second;
            update1(1,1,500001,l,m+num1[j]);
            update1(1,1,500001,l,m+num2[j]-d*l+u*(500002-l));
            update2(1,1,500001,l,m+num2[j]);
            update2(1,1,500001,l,m+num1[j]-u*(500002-l)+d*l);
            //debug(1,1,500001);
        }
        for(int j=0;j<v[i].size();j++)
        {
            //printf("%d %lld %lld\n",i,l[i],m[i]);
            m=v[i][j].second;
            update1(1,1,500001,l,m+num1[j]);
            update1(1,1,500001,l,m+num2[j]-d*l+u*(500002-l));
            update2(1,1,500001,l,m+num2[j]);
            update2(1,1,500001,l,m+num1[j]-u*(500002-l)+d*l);
            //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)));
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:118:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
salesman.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for(int j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
salesman.cpp:104:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |     scanf("%lld%lld%lld%lld",&n,&u,&d,&s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         scanf("%lld%lld%lld",&t_i,&l_i,&m_i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100