Submission #504002

#	Time	Username	Problem	Language	Result	Execution time	Memory
504002		79brue	Salesman (IOI09_salesman)	C++14	90 / 100	1821 ms	65540 KiB

salesman

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Market{
    int day; ll loc; ll w;

    bool operator<(const Market &r)const{
        return day == r.day ? loc < r.loc : day < r.day;
    }
};

stack<pair<ll*, ll> > stk;
struct segTree{
    ll tree[2000002];

    void init(int i, int l, int r){
        if(l==r){
            tree[i] = -1e9;
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m), init(i*2+1, m+1, r);
        tree[i] = -1e9;
    }

    void update(int i, int l, int r, int x, ll v){
        if(l==r){
            stk.push(make_pair(&tree[i], tree[i]));
            tree[i] = max(tree[i], v);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) update(i*2, l, m, x, v);
        else update(i*2+1, m+1, r, x, v);
        stk.push(make_pair(&tree[i], tree[i]));
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }

    ll query(int i, int l, int r, int s, int e){
        if(r<s || e<l) return -1e18;
        if(s<=l && r<=e) return tree[i];
        int m = (l+r)>>1;
        return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
    }
} treeU, treeD;

int n; ll u, d; int s;
Market arr[500002];

void reset(){
    while(!stk.empty()) stk.pop();
}

void rollback(){
    while(!stk.empty()){
        *(stk.top().first) = stk.top().second;
        stk.pop();
    }
}

int main(){
    scanf("%d %lld %lld %lld", &n, &u, &d, &s);
    for(int i=1; i<=n; i++){
        scanf("%d %lld %lld", &arr[i].day, &arr[i].loc, &arr[i].w);
    }
    sort(arr+1, arr+n+1);

    const int MAX = 500001;
    treeU.init(1, 1, MAX), treeD.init(1, 1, MAX);
    treeU.update(1, 1, MAX, s, -u*s);
    treeD.update(1, 1, MAX, s, d*s);
    for(int i=1; i<=n; i++){
        int j = i;
        while(arr[j+1].day == arr[i].day) j++;
        reset();
        if(i==j){
            ll val = max(treeU.query(1, 1, MAX, arr[i].loc, MAX) + arr[i].loc * u,
                         treeD.query(1, 1, MAX, 1, arr[i].loc) - arr[i].loc * d) + arr[i].w;
            treeU.update(1, 1, MAX, arr[i].loc, val-u*arr[i].loc);
            treeD.update(1, 1, MAX, arr[i].loc, val+d*arr[i].loc);
            continue;
        }

        vector<pair<ll, ll> > vec;
        for(int x=i; x<=j; x++){
            ll val = max(treeU.query(1, 1, MAX, arr[x].loc, MAX) + arr[x].loc * u,
                         treeD.query(1, 1, MAX, 1, arr[x].loc) - arr[x].loc * d) + arr[x].w;
            treeU.update(1, 1, MAX, arr[x].loc, val-u*arr[x].loc);
            treeD.update(1, 1, MAX, arr[x].loc, val+d*arr[x].loc);
            vec.push_back(make_pair(arr[x].loc, val));
        }
        rollback();
        for(int x=j; x>=i; x--){
            ll val = max(treeU.query(1, 1, MAX, arr[x].loc, MAX) + arr[x].loc * u,
                         treeD.query(1, 1, MAX, 1, arr[x].loc) - arr[x].loc * d) + arr[x].w;
            treeU.update(1, 1, MAX, arr[x].loc, val-u*arr[x].loc);
            treeD.update(1, 1, MAX, arr[x].loc, val+d*arr[x].loc);
        }
        for(auto p: vec){
            treeU.update(1, 1, MAX, p.first, p.second-u*p.first);
            treeD.update(1, 1, MAX, p.first, p.second+d*p.first);
        }
        i=j;
    }

    ll ans = max(treeU.query(1, 1, MAX, s, MAX) + s*u,
              treeD.query(1, 1, MAX, 1, s) - s*d);
    printf("%lld", ans);
}

Compilation message (stderr)

salesman.cpp: In function 'int main()':
salesman.cpp:65:28: warning: format '%lld' expects argument of type 'long long int*', but argument 5 has type 'int*' [-Wformat=]
   65 |     scanf("%d %lld %lld %lld", &n, &u, &d, &s);
      |                         ~~~^               ~~
      |                            |               |
      |                            long long int*  int*
      |                         %d
salesman.cpp:65:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     scanf("%d %lld %lld %lld", &n, &u, &d, &s);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
salesman.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |         scanf("%d %lld %lld", &arr[i].day, &arr[i].loc, &arr[i].w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 90 / 100