Submission #520440

#	Time	Username	Problem	Language	Result	Execution time	Memory
520440		ajpiano	Long Distance Coach (JOI17_coach)	C++17	100 / 100	166 ms	23896 KiB

coach

//https://oj.uz/problem/view/JOI17_coach
#include <bits/stdc++.h>

using namespace std;

#define f first
#define s second

typedef long long ll;
typedef pair<ll, ll> pi;

const ll inf = 2e18;

struct line{
    ll m, b;
    ll eval(ll x){
        return m*x+b;
    }
    bool cover(line a, ll l, ll r){
        return eval(l) <= a.eval(l) && eval(r) <= a.eval(r);
    }
    line(){
        m = 0; b = inf;
    }
};

const int mx = 2e5+5;

struct lc{
    lc *c[2]; line S;

    lc(){
        c[0] = c[1] = NULL; S = line();
    }

    void ex(int i){
        if(!c[i]) c[i] = new lc();
    }

    void add(line X, int l = 0, int r = mx){
        if(X.cover(S,l,r)){
            swap(X,S);
        }
        if(S.cover(X,l,r)) return;
        if(l == r) return;

        int mid = (l+r)>>1;
        if(X.eval(mid) <= S.eval(mid)) swap(X,S);

        if(X.eval(l) <= S.eval(l)) ex(0), c[0]->add(X,l,mid);
        else ex(1), c[1]->add(X,mid+1,r);
    }

    ll query(int pos, int l = 0, int r = mx){
        ll ans = S.eval(pos);
        int mid = (l+r)>>1;
        if(pos <= mid){
            if(c[0]) ans = min(ans,c[0]->query(pos, l, mid));
        }else{
            if(c[1]) ans = min(ans,c[1]->query(pos, mid+1, r));
        }
        return ans;
    }

}chull;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //remember to include destination in dp
    //remember to add driver cost
    ll x, w, t; int n,m; cin >> x >> n >> m >> w >> t; //Total time, cities, people, water cost, time interval

    vector<ll> stops(n+1); //where the coach stops
    for(int i = 0; i < n; i++) cin >> stops[i];
    stops[n] = x;
    sort(stops.begin(), stops.end());

    vector<pi> passengers(m+1); // water time, refund cost
    for(int i = 1; i <= m; i++) cin >> passengers[i].f >> passengers[i].s;
    sort(passengers.begin(), passengers.end());

    //find from where you can go back on a passenger
    vector<int> goback(m+1,-1);
    for(int i = n; i >= 0; i--){
        ll pos = stops[i]%t;
        pi fnd = {pos,0};
        int cur = lower_bound(passengers.begin(), passengers.end(), fnd) - passengers.begin()-1; //passenger you can go back from
        goback[cur] = i;
    }

    //find coefficient for each stop
    vector<ll> coe(n+1);
    for(int i = 0; i <= n; i++) coe[i] = w*(stops[i]/t);

    //find full cost for each passenger
    vector<ll> cost(m+1);
    for(int i = 0; i <= m; i++){
        cost[i] = w*((x-passengers[i].f)/t+1LL)-passengers[i].s;
    }

    ll ans = 0;
    //assume you refund everyone
    for(int i = 0; i <= m; i++) ans += passengers[i].s;
    //add driver cost
    ans += cost[0];

    vector<ll> dp(m+2);

    //do dp
    for(int i = m; i > 0; i--){
        dp[i] = cost[i]+dp[i+1];
        if(goback[i] != -1){
            ll m1 = coe[goback[i]];
            ll b1 = dp[i+1] - m1*(ll)(m-i-1);
            line cur; cur.m = m1, cur.b = b1;
            chull.add(cur,0,m);
        }
        dp[i] = min(dp[i], chull.query(m-i,0,m));
    }

    //give ans
    cout << ans+dp[1] << "\n";
    return 0;
}

• Subtask 1: 16 / 16
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 29 / 29