Submission #1139925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139925		dlguq0107	Salesman (IOI09_salesman)	C++20	100 / 100	524 ms	47404 KiB

salesman

#include<bits/stdc++.h>

using namespace std;

const int INF=1e9;
const int MAX=500005;

vector<pair<int,int>> r[MAX]; 

struct Seg{
    int arr[MAX], seg[4*MAX];

    Seg(){
       for(int i=0; i<MAX; i++) arr[i]=-INF;
       for(int i=0; i<4*MAX; i++) seg[i]=-INF;
    }

    int query(int l, int r, int nl=0, int nr=MAX-1, int node=1){
        if(r<nl||nr<l) return -INF;
        if(l<=nl&&nr<=r) return seg[node];
        int mid=nl+nr>>1;
        return max(query(l,r,nl,mid,node*2),query(l,r,mid+1,nr,node*2+1));
    }

    int update(int idx, int val, int nl=0, int nr=MAX-1, int node=1){
        if(idx<nl||nr<idx) return seg[node];
        if(nl==nr) return seg[node]=val;
        int mid=nl+nr>>1;
        return seg[node]=max(update(idx,val,nl,mid,node*2),update(idx,val,mid+1,nr,node*2+1));
    }
} up, down;

int main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int n, u, d, s;
    cin >> n >> u >> d >> s;
    s--;

    for(int i=0; i<n; i++){
        int t, l, m;
        cin >> t >> l >> m;
        r[--t].push_back({--l,m});
    }

    down.update(s,s*d);
    up.update(s,-s*u);
    for(int t=0; t<MAX; t++){
        if(r[t].empty()) continue;
        sort(r[t].begin(), r[t].end());

        vector<int> ud(r[t].size()), dd(r[t].size());
        for(int i=0; i<r[t].size(); i++){
            auto [l, m] = r[t][i];
            ud[i]=dd[i]=max(down.query(0,l-1)-l*d, up.query(l+1,MAX-1)+l*u)+m;
        }
        for(int i=1; i<r[t].size(); i++){
            auto [l, m] = r[t][i];
            auto [lp, mp] = r[t][i-1];
            dd[i]=max(dd[i],dd[i-1]-d*(l-lp)+m);
        }
        for(int i=r[t].size()-2; i>=0; i--){
            auto [l, m] = r[t][i];
            auto [lp, mp] = r[t][i+1];
            ud[i]=max(ud[i],ud[i+1]-u*(lp-l)+m);
        }
        for(int i=0; i<r[t].size(); i++){
            auto [l, m] = r[t][i];
            int mx=max(dd[i],ud[i]);
            down.update(l,mx+l*d);
            up.update(l,mx-l*u);
        }
    }

    cout << max({0,down.query(0,s-1)-s*d,up.query(s+1,MAX-1)+s*u});
}

• Subtask 1: 100 / 100