oj.uz

Submission #1087601

# Submission time Handle Problem Language Result Execution time Memory
1087601 2024-09-13T02:21:10 Z Seungni Treatment Project (JOI20_treatment) C++17
4 / 100
 83 ms 9192 KB 
#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 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};
    }
    
    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];
    
}

void solve() {
    cin >> N >> M;
    
    int sub_task1 = 1;
    
    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;
    }
    
    
    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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 8988 KB Output is correct
2 Correct 61 ms 9128 KB Output is correct
3 Correct 58 ms 9160 KB Output is correct
4 Correct 59 ms 9072 KB Output is correct
5 Correct 45 ms 9164 KB Output is correct
6 Correct 42 ms 9000 KB Output is correct
7 Correct 43 ms 9000 KB Output is correct
8 Correct 51 ms 9108 KB Output is correct
9 Correct 45 ms 9112 KB Output is correct
10 Correct 45 ms 9164 KB Output is correct
11 Correct 83 ms 9124 KB Output is correct
12 Correct 77 ms 9108 KB Output is correct
13 Correct 76 ms 9192 KB Output is correct
14 Correct 70 ms 9160 KB Output is correct
15 Correct 64 ms 9036 KB Output is correct
16 Correct 65 ms 9160 KB Output is correct
17 Correct 64 ms 9156 KB Output is correct
18 Correct 72 ms 9104 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 8988 KB Output is correct
2 Correct 61 ms 9128 KB Output is correct
3 Correct 58 ms 9160 KB Output is correct
4 Correct 59 ms 9072 KB Output is correct
5 Correct 45 ms 9164 KB Output is correct
6 Correct 42 ms 9000 KB Output is correct
7 Correct 43 ms 9000 KB Output is correct
8 Correct 51 ms 9108 KB Output is correct
9 Correct 45 ms 9112 KB Output is correct
10 Correct 45 ms 9164 KB Output is correct
11 Correct 83 ms 9124 KB Output is correct
12 Correct 77 ms 9108 KB Output is correct
13 Correct 76 ms 9192 KB Output is correct
14 Correct 70 ms 9160 KB Output is correct
15 Correct 64 ms 9036 KB Output is correct
16 Correct 65 ms 9160 KB Output is correct
17 Correct 64 ms 9156 KB Output is correct
18 Correct 72 ms 9104 KB Output is correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Halted 0 ms 0 KB -