Submission #1087701

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087701		Seungni	Treatment Project (JOI20_treatment)	C++17	9 / 100	96 ms	92744 KiB

treatment

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;

ll N, M, sz;
pair<ll, pair<pii, ll>> arr[100005];
vector<pii> graph[100005];
ll seg[200505 * 2];

void update(int pos, ll v) {
    pos += sz;
    seg[pos] = min(seg[pos], v);
    for (; pos > 0; pos >>= 1) seg[pos >> 1] = min(seg[pos], seg[pos ^ 1]);
    return;
}

ll query(int l, int r) {
    r++;
    ll ret = inf;
    for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ret = min(ret, seg[l++]);
        if (r & 1) ret = min(ret, seg[--r]);
    }
    return ret;
}

void Dijkstra(int S, vector<ll> &dist) {
    priority_queue<pii, vector<pii>, greater<>> pq;
    dist[S] = 0;
    pq.push({0, S});
    
    while (pq.size()) {
        pii t = pq.top();
        pq.pop();
        ll now = t.second, v = t.first;
        if (dist[now] < v) continue;
        
        for (auto &[next, cost]: graph[now]) {
            ll ncost = v + cost;
            if (dist[next] > ncost) {
                dist[next] = ncost;
                pq.push({ncost, next});
            }
        }
    }
}

void subtask_1() {
    vector<ll> v;
    v.push_back(0);
    v.push_back(1), v.push_back(N);
    for (int i = 0; i < M; i++) {
        v.push_back(arr[i].second.first.first);
        v.push_back(arr[i].second.first.second);
    }
    
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    
    sz = v.size();
    
    sort(arr, arr + M, [&](pair<ll, pair<pii, ll>> a, pair<ll, pair<pii, ll>> b) {
        return a.second.first.second < b.second.first.second;
    });
    for (int i = 0; i < M; i++) {
        ll L = arr[i].second.first.first, R = arr[i].second.first.second;
        L = lower_bound(v.begin(), v.end(), L) - v.begin();
        R = lower_bound(v.begin(), v.end(), R) - v.begin();
        arr[i].second.first = {L, R};
    }
    
    vector<ll> dp(sz + 5, inf);
    memset(seg, 0x3f, sizeof(seg));
    dp[0] = 0;
    update(0, dp[0]);
    
    for (int i = 0; i < M; i++) {
        ll l = arr[i].second.first.first, r = arr[i].second.first.second, c = arr[i].second.second;
        ll idx = lower_bound(v.begin(), v.end(), v[l] - 1) - v.begin();
        dp[r] = min(dp[r], query(idx, r) + c);
        update(r, dp[r]);
    }
    
    int idx = lower_bound(v.begin(), v.end(), N) - v.begin();
    if (dp[idx] == inf) cout << -1;
    else cout << dp[idx];
    return;
}

void subtask_2() {
    ll ans = inf;
    
    sort(arr, arr + M);
    
    for (int i = 0; i < (1 << M); i++) {
        vector<int> v;
        ll cost = 0;
        for (int j = 0; j < M; j++) {
            if (i & (1 << j)) v.push_back(j), cost += arr[j].second.second;
        }
        
        vector<pair<pii, ll>> now;
        now.push_back({{1, N}, 0});
        
        for (int j: v) {
            vector<pair<pii, ll>> nxt;
            ll T = arr[j].first, L = arr[j].second.first.first, R = arr[j].second.first.second;
            for (auto &[range, t]: now) {
                ll l = range.first, r = range.second;
                l -= T - t, l = max(l, 1LL);
                r += T - t, r = min(r, N);
                if (l < L) nxt.push_back({{l, min(r, L - 1)}, T});
                if (r > R) nxt.push_back({{max(l, R + 1), r}, T});
            }
            swap(nxt, now);
        }
        
        if (now.empty()) ans = min(ans, cost);
    }
    
    if (ans == inf) cout << -1;
    else cout << ans;
    
    return;
}

void subtask_3() {
    int S = M, E = M + 1;
    sort(arr, arr + M);
    for (int i = 0; i < M; i++) {
        ll t1 = arr[i].first, l1 = arr[i].second.first.first, r1 = arr[i].second.first.second, c1 = arr[i].second.second;
        if (l1 == 1) {
            graph[S].push_back({i, c1});
            graph[i].push_back({S, c1});
        }
        if (r1 == N) {
            graph[E].push_back({i, 0});
            graph[i].push_back({E, 0});
        }
        for (int j = i + 1; j < M; j++) {
            ll t2 = arr[j].first, l2 = arr[j].second.first.first, r2 = arr[j].second.first.second, c2 = arr[j].second.second;
            ll diff = t2 - t1;
            ll a = l1 + diff, b = r1 - diff;
            if (a > b) continue;
            if (b > r2) {
                swap(a, l2);
                swap(b, r2);
                c2 = c1;
            }
            if (b + 1 >= l2) {
                graph[i].push_back({j, c2});
                graph[j].push_back({i, c2});
            }
        }
    }
    
    vector<ll> dist(M + 5, inf);
    Dijkstra(S, dist);
    
    if (dist[E] == inf) cout << -1;
    else cout << dist[E];
    
    return;
}

void solve() {
    cin >> N >> M;
    
    int sub_task1 = 1, sub_task2 = (M <= 16), sub_task3 = (M <= 5000);
    
    for (int i = 0; i < M; i++) {
        ll T, L, R, C;
        cin >> T >> L >> R >> C;
        if (T != 1) sub_task1 = 0;
        arr[i] = {T, {{L, R}, C}};
    }
    
    if (sub_task1) {
        subtask_1();
        return;
    }
    
    if (sub_task2) {
        subtask_2();
        return;
    }
    
    if (sub_task3) {
        subtask_3();
        return;
    }
    
    return;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) solve();
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61