Submission #1306595

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306595		0917ba	Salesman (IOI09_salesman)	C++20	62 / 100	522 ms	52856 KiB

salesman

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

#ifdef LOCAL
#include "./algo-templates/debug.h"
#else
#define debug(...)
#define debugArr(...)
#endif

#define all(v) v.begin(),v.end()
#define mset(a, b) memset(a, b, sizeof(a))
#define sz(a) (int)(a).size()
#define X first
#define Y second
#define forr(i, n) for(int i = 0; i < (n); i++)
#define fors(i, s, e) for(int i = (s); i <= (e); i++)
#define fore(i, e, s) for(int i = (e); i >= (s); i--)
#define endl '\n'
#define int long long

using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vpi = vector<pi>;
using tp = array<int, 3>;
using ttp = array<int, 4>;
using vtp = vector<tp>;
using vttp = vector<ttp>;

const int dy[]={0, 1, 0, -1};
const int dx[]={1, 0, -1, 0};
const int inf=1e18, mod=1e9+7;
const double PI = acos(-1);
const int N=500'010;

template<class S, auto op, auto e>
class SegTree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>, "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>, "e must work as S()");

public:
    SegTree() : SegTree(0) {}
    explicit SegTree(int n) : SegTree(std::vector<S>(n, e())) {}
    explicit SegTree(const std::vector<S>& v) : _n(v.size()) {
        size = std::bit_ceil((unsigned int)_n+1);
        log = std::countr_zero((unsigned int)size);
        d = std::vector<S>(size << 1, e());
        for (int i = 1; i <= _n; i++) d[size + i] = v[i - 1];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void update(int p, S x) {
        assert(0 <= p && p <= _n);
        p |= size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p <= _n);
        return d[p + size];
    }

    S query(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S ret = e();
        l |= size;
        r |= size;

        while (l <= r) {
            if (l & 1) ret = op(ret, d[l++]);
            if (~r & 1) ret = op(ret, d[r--]);
            l >>= 1;
            r >>= 1;
        }
        return ret;
    }

    S all_prod() const { return d[1]; }

private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[k << 1], d[k << 1 | 1]); }
};

int e() { return -inf; }
int op(int i, int j) { return max(i, j); }
using Seg = SegTree<int, op, e>;
Seg seg[2][2];

int n, u, d, s, dp[N];
vtp mark;

void solve(){
    cin>>n>>u>>d>>s;
    forr(i, n){
        int a, b, c;
        cin>>a>>b>>c;
        mark.push_back({a, b, c});
    }
    mark.push_back({0, s, 0});
    mark.push_back({inf, s, 0});

    sort(all(mark));
    debug(mark);

    forr(i, 2) forr(j, 2){
        seg[i][j] = Seg(vi(N+10, -inf));
        seg[i][j].update(s, 0);
    }
    int l=1, r=1, ans=-inf;
    forr(i, n+2) dp[i] = -inf;
    dp[0] = 0;
    forr(k, 2){
        seg[k][0].update(s, d*s);
        seg[k][1].update(s, -u*s);
    }


    while(l <= n+1){
        while(r+1 <= n+1 && mark[l][1] == mark[r+1][1]) r++;
        debug(l, r);
        fors(i, l, r){ // k == 0 (순방향)
            const auto&[ti, li, mi] = mark[i];
            int p = seg[0][0].query(0, li) + mi - d*li;
            int q = seg[0][1].query(li, N-1) + mi + u*li;
            dp[i] = max(dp[i], max(p, q));
        }
        fore(i, r, l){ // k == 1 (역방향)
            const auto&[ti, li, mi] = mark[i];
            int p = seg[1][0].query(0, li) + mi - d*li;
            int q = seg[1][1].query(li, N-1) + mi + u*li;
            dp[i] = max(dp[i], max(p, q));
        }

        fors(i, l, r){
            const auto&[ti, li, mi] = mark[i];
            forr(k, 2){
                seg[k][0].update(li, dp[i] + d*li);
                seg[k][1].update(li, dp[i] - u*li);
            }
            debug(i, dp[i]);
        }
        l = r+1;
    }

    cout<<dp[n+1];
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
    return 0;
}

• Subtask 1: 62 / 100