Submission #1183725

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183725		Ahmed_Kaaniche	Long Distance Coach (JOI17_coach)	C++20	0 / 100	0 ms	328 KiB

coach

#include <bits/stdc++.h>
using namespace std;

#define endl "\n"
#define ll long long
#define fi first
#define se second
#define pb push_back

ll X, n, m, w, t, sz = 1;
vector<ll> stn;
vector<pair<ll, ll>> arr;
vector<ll> tree, lazy;
vector<ll> tree2, lazy2;

// ----- Lazy Propagation 1 -----
void apply(ll k) {
    tree[k] = 0;
    lazy[k] = 0;
}

void propagate(ll k) {
    if (lazy[k] != -1) {
        apply(2 * k);
        apply(2 * k + 1);
        lazy[k] = -1;
    }
}

void build() {
    for (int i = 0; i < m; ++i) {
        tree[i + sz] = arr[i].se;
    }
    for (int i = sz - 1; i >= 1; --i) {
        tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
}

void update(ll a, ll b, ll x, ll y, ll k) {
    if (y < a || x > b)
        return;
    if (x >= a && y <= b) {
        apply(k);
        return;
    }
    propagate(k);
    ll mid = (x + y) / 2;
    update(a, b, x, mid, 2 * k);
    update(a, b, mid + 1, y, 2 * k + 1);
    tree[k] = tree[2 * k] + tree[2 * k + 1];
}

ll query(ll a, ll b, ll x, ll y, ll k) {
    if (y < a || x > b)
        return 0;
    if (x >= a && y <= b)
        return tree[k];
    propagate(k);
    ll mid = (x + y) / 2;
    return query(a, b, x, mid, 2 * k) + query(a, b, mid + 1, y, 2 * k + 1);
}



//----- Lazy Propagation 2 -----
void apply2(ll k) {
    tree2[k] = 0;
    lazy2[k] = 0;
}

void propagate2(ll k) {
    if (lazy2[k] != -1) {
        apply2(2 * k);
        apply2(2 * k + 1);
        lazy2[k] = -1;
    }
}

void build2() {
    for (int i = 0; i < m; ++i) {
        if (arr[i].fi < X % t)
            tree2[i + sz] = 1;
    }
    for (int i = sz - 1; i >= 1; --i) {
        tree2[i] = tree2[2 * i] + tree2[2 * i + 1];
    }
}

void update2(ll a, ll b, ll x, ll y, ll k) {
    if (y < a || x > b)
        return;
    if (x >= a && y <= b) {
        apply2(k);
        return;
    }
    propagate2(k);
    ll mid = (x + y) / 2;
    update2(a, b, x, mid, 2 * k);
    update2(a, b, mid + 1, y, 2 * k + 1);
    tree2[k] = tree2[2 * k] + tree2[2 * k + 1];
}

ll query2(ll a, ll b, ll x, ll y, ll k) {
    if (y < a || x > b)
        return 0;
    if (x >= a && y <= b)
        return tree2[k];
    propagate2(k);
    ll mid = (x + y) / 2;
    return query2(a, b, x, mid, 2 * k) + query2(a, b, mid + 1, y, 2 * k + 1);
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    cin >> X >> n >> m >> w >> t;
    while (sz < m) sz *= 2;
    stn.resize(n + 1);
    arr.resize(m);
    tree.assign(2 * sz, 0);
    lazy.assign(2 * sz, -1);
    tree2.assign(2 * sz, 0);
    lazy2.assign(2 * sz, -1);
    
    for (int i = 0; i < n; ++i) {
        cin >> stn[i];
    }
    stn[n] = X;
    for (int i = 0; i < m; ++i) {
        cin >> arr[i].fi >> arr[i].se;
    }
    
    sort(stn.begin(), stn.end());
    sort(arr.begin(), arr.end());
    
    build();
    build2();
    
    ll ans = 0, nb = m + 1;
    ll idx = 0, l = 0;
    bool v = true;
    
    for (int i = 0; i <= n; ++i) {
        if (idx == 0)
            ans += ((stn[i] - l) / t) * nb * w + w;
        
        //1
        l = (stn[i] / t) * t;
        ll diff = stn[i] - l;
        ll rst = ((X - l) / t);
        ll r = -1;
        v = true;
        
        for (int j = 0; j < m; ++j) {
            if (arr[j].fi == -2)
                continue;
            
            if (arr[j].fi == -1) {
                v = !v;
                continue;
            }
            if (v && arr[j].fi < diff)
                r = j;
        }
        
        //2
        idx = r + 1;
        if (r != -1) {
            v = true;
            for (int j = r; j >= 0; --j) {
                if (arr[j].fi == -2) {
                    if (r == j)
                        r = j - 1;
                    continue;
                }
                if (arr[j].fi == -1) {
                    if (r == j)
                        r = j - 1;
                    v = !v;
                    continue;
                }
                
                if (v) {
                    ll sum1 = query(j, r, 0, sz - 1, 1);
                    ll sum2 = (rst * (r - j + 1) + query2(j, r, 0, sz - 1, 1)) * w;
                    if (sum1 < sum2) {
                        ans += sum1;
                        nb -= r - j + 1;
                        update(j, r, 0, sz - 1, 1);
                        update2(j, r, 0, sz - 1, 1);
                        if (r == j)
                            arr[j].fi = -2;
                        else {
                            arr[j].fi = -1;
                            arr[r].fi = -1;
                        }
                        r = j - 1;
                    } else {
                        ans += w;
                    }
                }
                else if (r == j) {
                    r = j - 1;
                }
            }
        }
        
        //3
        if (i < n) {
            ll nxt = stn[i + 1];
            if (l + t < nxt) {
                for (; idx < m; ++idx) {
                    if (arr[idx].fi == -2)
                        continue;
                    if (arr[idx].fi == -1) {
                        v = !v;
                        continue;
                    }
                    if (v && l + arr[idx].fi < nxt) {
                        ans += w;
                    }
                }
                idx = 0;
                l += t;
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

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