Submission #967874

#	Time	Username	Problem	Language	Result	Execution time	Memory
967874		Mike_Vu	Long Distance Coach (JOI17_coach)	C++14	100 / 100	245 ms	23892 KiB

coach

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

//const ll mod = 1e9+7;

bool maximize(ll &x, ll y ){
    if (x < y) {x = y; return true;};
    return false;
}
bool minimize(ll &x, ll y){
    if (x > y) {x = y; return true;}
    return false;
}
//void add(ll &x, ll y ){
//    x += y;
//    if (x >= mod) x -= mod;
//}
//void sub(ll &x, ll y) {
//    x -= y;
//    if (x < 0) x += mod;
//}

struct Line{
    ll m, b;
    Line(ll slope = 0, ll intercept = 1e18+7){
        m = slope;
        b = intercept;
    }
    ll operator () (ll x){return m*x+b;}
};

struct LICHAO{
    vector<Line> tr;
    int trsz;
    LICHAO(int n = 0) {
        trsz = 1;
        while (trsz <= n) {
            trsz *= 2;
        }
        tr.assign(trsz*2, Line());
    }
    void update(Line a, int l, int r, int id){
        if (l + 1 == r) {
            if (tr[id](l) > a(l)) tr[id] = a;
            return;
        }
        int mid = (l+r) >> 1;
        if (tr[id].m < a.m) swap(tr[id], a);
        if (tr[id](mid) > a(mid)) {
            swap(tr[id], a);
            update(a, l, mid, id*2);
        }
        else {
            update(a, mid+1, r, id*2+1);
        }
    }
    ll query(ll x, int l, int r, int id) {
        if (l+1 == r) {
            return tr[id](x);
        }
        int mid = (l+r) >> 1;
        ll res = tr[id](x);
        if (x <= mid) return min(res, query(x, l, mid, id*2));
        else return min(res, query(x, mid+1, r, id*2+1));
    }
} cht;

const int maxn = 2e5+5;
int n, m;
ll x, lapse, w;
ll refill[maxn], a[maxn], b[maxn], dp[maxn], ps[maxn];
pii temp[maxn];

bool cmp1(ll a, ll b) {
    if ((a%lapse) != (b%lapse)) return (a%lapse) < (b%lapse);
    else return (a<b);
}
bool cmp2(pii a, pii b){
    return (a.fi <= b.fi);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> x >> n >> m >> w >> lapse;
    for (int i = 1; i <= n; i++) {
        cin >> refill[i];
    }
    ps[0] = 0;
    for (int i = 1; i <= m; i++) {
        cin >> temp[i].fi >> temp[i].se;
    }
    sort(temp+1, temp+m+1, cmp2);
    for (int i = 1; i <= m; i++) {
        a[i] = temp[i].fi;
        b[i] = temp[i].se;
        ps[i] = ps[i-1] + b[i];
    }
    refill[++n] = x;
    sort(refill+1, refill+n+1, cmp1);
    int j = n+1;
    dp[m+1] = 0;
    cht = LICHAO(m);
    for (int i = m; i > 0; i--){
        dp[i] = dp[i+1] + w*((x-a[i])/lapse+1);
//        system("pause");
        while (j-1 > 0 && (refill[j-1]%lapse) > a[i]) {
            --j;
            cht.update(Line(-w*(refill[j]/lapse), w*(refill[j]/lapse)*(i+1)+ps[i]+dp[i+1]),1,cht.trsz,1);
        }
//        system("pause");
        minimize(dp[i], cht.query(i, 1,cht.trsz,1)-ps[i-1]);
//        cout << dp[i] << ' ';
    }
    cout << dp[1]+(x/lapse+1)*w; //driver
}
/*
19 1 4 8 7
10
1 20
2 10
4 5
6 5

105 3 5 9 10
59
68
71
4 71
6 32
7 29
3 62
2 35
*/

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