Submission #1183727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183727		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

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

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);
}

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);
    
    cin >> X >> n >> m >> w >> t;
    while(sz < m) sz *= 2;
    
    stn.resize(n + 1);
    arr.resize(m);
    arrStatus.assign(m, 0);
    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;
    ll nb = m + 1;
    int idx = 0;
    ll l = 0;
    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);
        int r = -1;
        bool v = true;
        for (int j = 0; j < m; j++){
            if(arrStatus[j] == 2) continue;
            if(arrStatus[j] == 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(arrStatus[j] == 2){
                    if(r == j) r = j - 1;
                    continue;
                }
                if(arrStatus[j] == 1){
                    if(r == j) r = j - 1;
                    v = !v;
                    continue;
                }
                if(v){
                    ll costSegment = query(j, r, 0, sz - 1, 1);
                    ll countFlags = query2(j, r, 0, sz - 1, 1);
                    ll costAlt = (rst * (r - j + 1) + countFlags) * w;
                    if(costSegment < costAlt){
                        ans += costSegment;
                        nb -= (r - j + 1);
                        update(j, r, 0, sz - 1, 1);
                        update2(j, r, 0, sz - 1, 1);
                        if(r == j)
                            arrStatus[j] = 2;
                        else{
                            arrStatus[j] = 1;
                            arrStatus[r] = 1;
                        }
                        r = j - 1;
                    } else {
                        ans += w;
                    }
                } else if(r == j)
                    r = j - 1;
            }
        }
        //2
        if(i < n){
            ll nxt = stn[i+1];
            if(l + t < nxt){
                v = true;
                for(; idx < m; idx++){
                    if(arrStatus[idx] == 2) continue;
                    if(arrStatus[idx] == 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