Submission #1087594

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087594		Seungni	Treatment Project (JOI20_treatment)	C++17	4 / 100	89 ms	12372 KiB

treatment

#include <bits/stdc++.h>

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

ll N, M, sz;
pair<ll, pair<pii, ll>> arr[100005];
ll dp[200505];
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 solve() {
    cin >> N >> M;
    vector<ll> v;
    v.push_back(0);
    v.push_back(1), v.push_back(N);
    
    for (int i = 0; i < M; i++) {
        ll T, L, R, C;
        cin >> T >> L >> R >> C;
        v.push_back(L), v.push_back(R);
        arr[i] = {T, {{L, R}, C}};
    }
    
    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};
    }
    
    memset(dp, 0x3f, sizeof(dp));
    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;
}

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: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61