Submission #1243489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243489		meisgood	Salesman (IOI09_salesman)	C++20	100 / 100	1105 ms	59120 KiB

salesman

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector <pair<int,int>> v[500003] ;
struct segt {
  int seg[2000003] ;
  void build(){
    for (int i = 0 ; i < 2000003 ; i ++) seg[i]=-LLONG_MAX/4 ;
  }
  void upd(int id,int l,int r,int x,int v){
    if (l==r&&l==x) seg[id]=max(seg[id],v) ;
    else if (l>x||r<x) ;
    else {
      int md=(l+r)/2 ;
      upd(id*2,l,md,x,v) ;
      upd(id*2+1,md+1,r,x,v) ;
      seg[id]=max(seg[id*2],seg[id*2+1]) ;
    }
  }
  int qq(int id,int l,int r,int ql,int qr){
    if (ql<=l&&r<=qr) return seg[id] ;
    else if (l>qr||r<ql) return -LLONG_MAX/4 ;
    else {
      int md=(l+r)/2 ;
      return max(qq(id*2,l,md,ql,qr),qq(id*2+1,md+1,r,ql,qr)) ;
    }
  }
} ;
const int m=500001 ;
signed main() {
  int n,u,d,s,i,j ;
  cin >> n >> u >> d >> s ;
  u=-u,d=-d ;
  for (i = 0 ; i < n ; i ++){
    int a,b,c ;
    cin >> a >> b >> c ;
    v[a].push_back({b,c}) ;
  }
  v[500001].push_back({s,0}) ;
  segt ups,dos ;
  ups.build() ;
  dos.build() ;
  ups.upd(1,1,m,s,d*(m-s)) ;
  dos.upd(1,1,m,s,u*s) ;
  for (i = 1 ; i <= 500001 ; i ++){
    if (v[i].size()==0) ;
    // else if (v[i].size()==1){
      
    // }
    else {
      sort(v[i].begin(),v[i].end(),greater<pair<int,int>>()) ;
      int mx=-LLONG_MAX/4 ;
      vector <pair<int,int>> vvv ;
      int nw=0 ;
      for (auto [a,b] : v[i]){
        mx=max(mx,ups.qq(1,1,m,1,a)-d*(m-a)+u*a-nw) ;
        mx=max(mx,dos.qq(1,1,m,a,m)-u*a+u*a-nw) ;
        nw+=b ;
        vvv.push_back({a,mx-u*a+nw}) ;
      }
      reverse(v[i].begin(),v[i].end()) ;
      mx=-LLONG_MAX/4 ;
      vector <pair<int,int>> vvv2 ;
      nw=0 ;
      for (auto [a,b] : v[i]){
        mx=max(mx,dos.qq(1,1,m,a,m)-u*a+d*(m-a)-nw) ;
        mx=max(mx,ups.qq(1,1,m,1,a)-d*(m-a)+d*(m-a)-nw) ;
        nw+=b ;
        // cout << mx << endl ;
        vvv2.push_back({a,mx-d*(m-a)+nw}) ;
      }
      for (auto [a,b] : vvv){
        ups.upd(1,1,m,a,b+d*(m-a)) ;
        dos.upd(1,1,m,a,b+u*a) ;
      }
      for (auto [a,b] : vvv2){
        ups.upd(1,1,m,a,b+d*(m-a)) ;
        dos.upd(1,1,m,a,b+u*a) ;
      }
      // for (auto [a,b] : v[i]) cout << ups.qq(1,1,m,a,a)-d*(m-a) << " " ; cout << endl ;
    }
  }
  cout << ups.qq(1,1,m,s,s)-d*(m-s) << endl ;
  return 0;
}

• Subtask 1: 100 / 100