Submission #596271

#	Time	Username	Problem	Language	Result	Execution time	Memory
596271		mosiashvililuka	Salesman (IOI09_salesman)	C++14	100 / 100	691 ms	52268 KiB

salesman

#include<bits/stdc++.h>
using namespace std;
const long long N=-999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,U,D,S,seglf[2000009],segrg[2000009],l,r,z,za,X[500009],pas,Y[500009],lf[500009],rg[500009];
vector <pair <long long, long long> > v[500009];
void UPD(int q, int w){
    long long qw=w-q*D;
    int rr=za+q-1;
    segrg[rr]=qw;rr/=2;
    while(rr!=0){
        segrg[rr]=max(segrg[rr*2],segrg[rr*2+1]);
        rr/=2;
    }
    qw=w+q*U;
    rr=za+q-1;
    seglf[rr]=qw;rr/=2;
    while(rr!=0){
        seglf[rr]=max(seglf[rr*2],seglf[rr*2+1]);
        rr/=2;
    }
}
void readlf(int q, int w, int rr){
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        z=max(z,seglf[rr]);
        return;
    }
    readlf(q,(q+w)/2,rr*2);
    readlf((q+w)/2+1,w,rr*2+1);
}
void readrg(int q, int w, int rr){
    if(q>r||w<l) return;
    if(q>=l&&w<=r){
        z=max(z,segrg[rr]);
        return;
    }
    readrg(q,(q+w)/2,rr*2);
    readrg((q+w)/2+1,w,rr*2+1);
}
int main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>a>>U>>D>>S;swap(U,D);
    for(i=1; i<=a; i++){
        cin>>c>>d>>e;
        v[c].push_back({d,e});
    }
    za=1;
    while(za<500001) za*=2;
    for(i=0; i<=za*2; i++){
        seglf[i]=segrg[i]=N;
    }
    UPD(S,0);
    for(ii=1; ii<=500001; ii++){
        if(v[ii].size()==0) continue;
        sort(v[ii].begin(),v[ii].end());
        for(j=0; j<v[ii].size(); j++){
            c=v[ii][j].first;d=v[ii][j].second;
            l=1;r=c;z=N;
            readlf(1,za,1);
            z=z-c*U+d;
            X[c]=z;

            l=c;r=500001;z=N;
            readrg(1,za,1);
            z=z+c*D+d;
            X[c]=max(X[c],z);
        }

        /*for(j=0; j<v[ii].size(); j++){
            c=v[ii][j].first;d=v[ii][j].second;
            UPD(c,X[c]);
        }*/
        zx=N;
        for(j=0; j<v[ii].size(); j++){
            c=v[ii][j].first;d=v[ii][j].second;
            zx+=d;
            zx=max(zx,X[c]+c*U);
            Y[c]=zx-c*U;
        }
        zx=N;
        for(j=v[ii].size()-1; j>=0; j--){
            c=v[ii][j].first;d=v[ii][j].second;
            zx+=d;
            zx=max(zx,X[c]-c*D);
            Y[c]=max(Y[c],zx+c*D);
        }
        /*zx=N;
        for(j=0; j<v[ii].size(); j++){
            c=v[ii][j].first;d=v[ii][j].second;
            zx+=d;
            zx=max(zx,X[c]+c*U*2LL);
            lf[c]=zx-c*U;
        }
        zx=N;
        for(j=v[ii].size()-1; j>=0; j--){
            c=v[ii][j].first;d=v[ii][j].second;
            zx+=d;
            zx=max(zx,X[c]-c*D*2LL);
            rg[c]=zx+c*D;
        }
        //
        zx=N;
        for(j=v[ii].size()-1; j>=0; j--){
            c=v[ii][j].first;d=v[ii][j].second;
            zx+=d;
            Y[j]=max(Y[j],zx+c*D);
            zx=max(zx,rg[c]);
        }
        zx=N;
        for(j=0; j<v[ii].size(); j++){
            c=v[ii][j].first;d=v[ii][j].second;
            zx+=d;
            Y[j]=max(Y[j],zx-c*U);
            zx=max(zx,lf[c]);
        }*/

        //

        for(j=0; j<v[ii].size(); j++){
            c=v[ii][j].first;d=v[ii][j].second;
            X[c]=max(X[c],Y[c]);
            UPD(c,X[c]);
        }
    }

    c=S;
    l=1;r=c;z=N;
    readlf(1,za,1);
    z=z-c*U;
    pas=max(pas,z);
    l=c;r=500001;z=N;
    readrg(1,za,1);
    z=z+c*D;
    pas=max(pas,z);
    cout<<pas;
    return 0;
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:56:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(j=0; j<v[ii].size(); j++){
      |                  ~^~~~~~~~~~~~~
salesman.cpp:74:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for(j=0; j<v[ii].size(); j++){
      |                  ~^~~~~~~~~~~~~
salesman.cpp:119:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(j=0; j<v[ii].size(); j++){
      |                  ~^~~~~~~~~~~~~

• Subtask 1: 100 / 100