Submission #335461

#	Time	Username	Problem	Language	Result	Execution time	Memory
335461		HynDuf	Salesman (IOI09_salesman)	C++11	100 / 100	1832 ms	29952 KiB

salesman

#include <bits/stdc++.h>

#define task "S"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int N = 5e5 + 2, INF = 2e9 + 1;
int n, D, U, S, dp[N], bitLD[N], bitRU[N], ndp[N];
struct Event
{
    int days, pos, money;
    bool operator < (const Event &oth)
    {
        return days < oth.days || (days == oth.days && pos < oth.pos);
    }
};
vector<Event> eve;
void updLD(int p, int v)
{
    for (; p < N; p += p & -p) bitLD[p] = max(bitLD[p], v);
}
int queryLD(int p)
{
    int res = -INF;
    for (; p; p -= p & -p) res = max(res, bitLD[p]);
    return res;
}
void updRU(int p, int v)
{
    for (; p; p -= p & -p) bitRU[p] = max(bitRU[p], v);
}
int queryRU(int p)
{
    int res = -INF;
    for (; p < N; p += p & -p) res = max(res, bitRU[p]);
    return res;
}
struct IT
{
    vi it, lz;
    IT(int nn) {it.assign(nn << 2, -INF); lz.assign(nn << 2, 0);}
    void dolz(int id, int l, int r)
    {
        if (lz[id] == 0 || it[id] == -INF) return;
        it[id] += lz[id];
        if (l != r)
        {
            lz[id << 1] += lz[id];
            lz[(id << 1) | 1] += lz[id];
        }
        lz[id] = 0;
    }
    void update(int id, int l, int r, int L, int R, int v, int ty)
    {
        dolz(id, l, r);
        if (l > R || r < L) return;
        if (L <= l && r <= R)
        {
            if (ty == 0)
            {
                assert(L == R);
                it[id] = v;
            } else
            {
                lz[id] += v;
                dolz(id, l, r);
            }
            return;
        }
        int m = (l + r) >> 1;
        update(id << 1, l, m, L, R, v, ty);
        update((id << 1) | 1, m + 1, r, L, R, v, ty);
        it[id] = max(it[id << 1], it[(id << 1) | 1]);
    }
    int query(int id, int l, int r, int L, int R)
    {
        dolz(id, l, r);
        if (l > R || r < L) return -INF;
        if (L <= l && r <= R) return it[id];
        int m = (l + r) >> 1;
        return max(query(id << 1, l, m, L, R), query((id << 1) | 1, m + 1, r, L, R));
    }
    void rollback(int id, int l, int r)
    {
        lz[id] = 0, it[id] = -INF;
        if (l == r) return;
        int m = (l + r) >> 1;
        if (it[id << 1] != -INF || lz[id << 1] != 0) rollback(id << 1, l, m);
        if (it[(id << 1) | 1] != -INF || lz[(id << 1) | 1] != 0) rollback((id << 1) | 1, m + 1, r);
    }
};
int main()
{
#ifdef HynDuf
    freopen(task".in", "r", stdin);
    //freopen(task".out", "w", stdout);
#else
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
    cin >> n >> U >> D >> S;
    eve.assign(n + 1, {});
    rep(i, 1, n) cin >> eve[i].days >> eve[i].pos >> eve[i].money;
    fill(bitLD + 1, bitLD + N, -INF);
    fill(bitRU + 1, bitRU + N, -INF);
    IT seg(N);
    sort(1 + all(eve));
    updLD(S, D * S);
    updRU(S, -U * S);
    for (int i = 1, j = 1; i <= n; i = j)
    {
        while (j <= n && eve[j].days == eve[i].days) j++;
        rep(k, i, j - 1)
        {
            const Event &E = eve[k];
            dp[k] = max(queryLD(E.pos) - D * E.pos, queryRU(E.pos) + U * E.pos) + E.money;
            ndp[k] = max(dp[k], seg.query(1, 1, N - 1, 1, E.pos - 1) + E.money - D * E.pos);
            seg.update(1, 1, N - 1, E.pos, E.pos, dp[k] + D * E.pos, 0);
            seg.update(1, 1, N - 1, 1, E.pos - 1, E.money, 1);
        }
        seg.rollback(1, 1, N - 1);
        Rep(k, j - 1, i)
        {
            const Event &E = eve[k];
            ndp[k] = max(ndp[k], seg.query(1, 1, N - 1, E.pos + 1, N - 1) + E.money + U * E.pos);
            seg.update(1, 1, N - 1, E.pos, E.pos, dp[k] - U * E.pos, 0);
            seg.update(1, 1, N - 1, E.pos + 1, N - 1, E.money, 1);
            updLD(E.pos, ndp[k] + D * E.pos);
            updRU(E.pos, ndp[k] - U * E.pos);
            dp[k] = ndp[k];
        }
        seg.rollback(1, 1, N - 1);
    }
    int ans = 0;
    rep(i, 1, n) ans = max(ans, dp[i] - ((eve[i].pos < S) ? D * (S - eve[i].pos) : U * (eve[i].pos - S)));
    cout << ans;
    return 0;
}

• Subtask 1: 100 / 100