oj.uz

Submission #487945

# Submission time Handle Problem Language Result Execution time Memory
487945 2021-11-17T07:33:22 Z ToroTN Salesman (IOI09_salesman) C++14
62 / 100
 978 ms 46560 KB 
#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,num2;
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++)
        {
            //printf("%d %lld %lld\n",i,l[i],m[i]);
            l=v[i][j].first;
            m=v[i][j].second;
            num1=query1(1,1,500001,l,500001);
            num2=query2(1,1,500001,1,l);
            update1(1,1,500001,l,m+num1);
            update1(1,1,500001,l,m+num2-d*l+u*(500002-l));
            update2(1,1,500001,l,m+num2);
            update2(1,1,500001,l,m+num1-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)));
        }
    }
    printf("%lld\n",max(query2(1,1,500001,1,s)-d*s,query1(1,1,500001,s,500001)-u*(500002-s)));
}

Compilation message

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: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
62.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 28364 KB Output is correct
2 Correct 26 ms 28372 KB Output is correct
3 Correct 26 ms 28432 KB Output is correct
4 Correct 27 ms 28464 KB Output is correct
5 Correct 24 ms 28620 KB Output is correct
6 Correct 61 ms 29380 KB Output is correct
7 Correct 118 ms 30908 KB Output is correct
8 Correct 210 ms 33308 KB Output is correct
9 Correct 330 ms 35496 KB Output is correct
10 Correct 510 ms 40388 KB Output is correct
11 Correct 624 ms 40340 KB Output is correct
12 Correct 796 ms 43524 KB Output is correct
13 Correct 779 ms 43520 KB Output is correct
14 Correct 926 ms 46524 KB Output is correct
15 Correct 810 ms 46560 KB Output is correct
16 Correct 978 ms 46524 KB Output is correct
17 Correct 27 ms 28364 KB Output is correct
18 Incorrect 24 ms 28368 KB Output isn't correct
19 Incorrect 20 ms 28432 KB Output isn't correct
20 Incorrect 21 ms 28492 KB Output isn't correct
21 Incorrect 27 ms 28492 KB Output isn't correct
22 Incorrect 25 ms 28568 KB Output isn't correct
23 Incorrect 24 ms 28576 KB Output isn't correct
24 Incorrect 24 ms 28492 KB Output isn't correct
25 Incorrect 159 ms 30916 KB Output isn't correct
26 Incorrect 313 ms 32996 KB Output isn't correct
27 Incorrect 449 ms 34572 KB Output isn't correct
28 Incorrect 523 ms 34744 KB Output isn't correct
29 Incorrect 689 ms 35780 KB Output isn't correct
30 Incorrect 698 ms 36088 KB Output isn't correct