제출 #596209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
596209		mosiashvililuka	Salesman (IOI09_salesman)	C++14	60 / 100	788 ms	56996 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;
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);
            //cout<<z<<"\n";
            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]);
            //cout<<c<<" "<<X[c]<<"\n";
        }
    }

    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;
}

컴파일 시 표준 에러 (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:70: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]
   70 |         for(j=0; j<v[ii].size(); j++){
      |                  ~^~~~~~~~~~~~~

• Subtask 1: 60 / 100