oj.uz

Submission #596271

# Submission time Handle Problem Language Result Execution time Memory
596271 2022-07-14T14:29:51 Z mosiashvililuka Salesman (IOI09_salesman) C++14
100 / 100
 691 ms 52268 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 15 ms 28456 KB Output is correct
3 Correct 15 ms 28588 KB Output is correct
4 Correct 17 ms 28596 KB Output is correct
5 Correct 18 ms 28756 KB Output is correct
6 Correct 43 ms 37040 KB Output is correct
7 Correct 85 ms 38012 KB Output is correct
8 Correct 152 ms 39576 KB Output is correct
9 Correct 211 ms 41036 KB Output is correct
10 Correct 341 ms 45840 KB Output is correct
11 Correct 421 ms 45840 KB Output is correct
12 Correct 551 ms 48964 KB Output is correct
13 Correct 548 ms 49044 KB Output is correct
14 Correct 691 ms 52116 KB Output is correct
15 Correct 592 ms 52096 KB Output is correct
16 Correct 687 ms 52268 KB Output is correct
17 Correct 14 ms 28452 KB Output is correct
18 Correct 14 ms 28564 KB Output is correct
19 Correct 16 ms 28588 KB Output is correct
20 Correct 17 ms 28748 KB Output is correct
21 Correct 16 ms 28568 KB Output is correct
22 Correct 18 ms 28676 KB Output is correct
23 Correct 18 ms 28756 KB Output is correct
24 Correct 18 ms 28788 KB Output is correct
25 Correct 116 ms 38564 KB Output is correct
26 Correct 212 ms 40564 KB Output is correct
27 Correct 333 ms 43328 KB Output is correct
28 Correct 375 ms 42712 KB Output is correct
29 Correct 510 ms 45648 KB Output is correct
30 Correct 484 ms 46428 KB Output is correct