oj.uz

Submission #152783

# Submission time Handle Problem Language Result Execution time Memory
152783 2019-09-09T13:41:21 Z dolphingarlic Pinball (JOI14_pinball) C++14
51 / 100
 1000 ms 98660 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Barrier {
    int a, b, c, d;
} brs[100000];
set<int> xs;
map<int, int> compressed;
ll segtree[8080808], dp1[100000], dp2[100000];
int m, n;

void update(int pos, ll val, int node = 1, int l = 1, int r = xs.size()) {
    if (l == r) segtree[node] = min(segtree[node], val);
    else {
        int mid = (l + r) / 2;
        if (pos > mid) update(pos, val, node * 2 + 1, mid + 1, r);
        else update(pos, val, node * 2, l, mid);
        segtree[node] = min(segtree[node * 2], segtree[node * 2 + 1]);
    }
}
ll query(int x, int y, int node = 1, int l = 1, int r = xs.size()) {
    if (x > r || y < l) return LLONG_MAX / m;
    else if (x <= l && y >= r) return segtree[node];
    else {
        int mid = (l + r) / 2;
        return min(query(x, y, node * 2, l, mid), query(x, y, node * 2 + 1, mid + 1, r));
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n;
    xs.insert(1);
    xs.insert(n);
    FOR(i, 0, m) {
        cin >> brs[i].a >> brs[i].b >> brs[i].c >> brs[i].d;
        xs.insert(brs[i].a); xs.insert(brs[i].b); xs.insert(brs[i].c);
    }
    int indx = 1;
    for (int i : xs) {
        compressed[i] = indx++;
    }

    fill(segtree, segtree + 8080808, LLONG_MAX / m);
    update(1, 0);
    FOR(i, 0, m) {
        dp1[i] = query(compressed[brs[i].a], compressed[brs[i].b]) + brs[i].d;
        update(compressed[brs[i].c], dp1[i]);
    }

    fill(segtree, segtree + 8080808, LLONG_MAX / m);
    update(xs.size(), 0);
    FOR(i, 0, m) {
        dp2[i] = query(compressed[brs[i].a], compressed[brs[i].b]) + brs[i].d;
        update(compressed[brs[i].c], dp2[i]);
    }

    ll ans = LLONG_MAX;
    FOR(i, 0, m) ans = min(ans, dp1[i] + dp2[i] - brs[i].d);
    if (ans < LLONG_MAX / m) cout << ans;
    else cout << -1;
    return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63608 KB Output is correct
2 Correct 63 ms 63736 KB Output is correct
3 Correct 63 ms 63608 KB Output is correct
4 Correct 63 ms 63608 KB Output is correct
5 Correct 63 ms 63608 KB Output is correct
6 Correct 63 ms 63608 KB Output is correct
7 Correct 63 ms 63564 KB Output is correct
8 Correct 64 ms 63652 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63608 KB Output is correct
2 Correct 63 ms 63736 KB Output is correct
3 Correct 63 ms 63608 KB Output is correct
4 Correct 63 ms 63608 KB Output is correct
5 Correct 63 ms 63608 KB Output is correct
6 Correct 63 ms 63608 KB Output is correct
7 Correct 63 ms 63564 KB Output is correct
8 Correct 64 ms 63652 KB Output is correct
9 Correct 71 ms 63756 KB Output is correct
10 Correct 64 ms 63688 KB Output is correct
11 Correct 64 ms 63608 KB Output is correct
12 Correct 64 ms 63736 KB Output is correct
13 Correct 64 ms 63736 KB Output is correct
14 Correct 64 ms 63608 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63608 KB Output is correct
2 Correct 63 ms 63736 KB Output is correct
3 Correct 63 ms 63608 KB Output is correct
4 Correct 63 ms 63608 KB Output is correct
5 Correct 63 ms 63608 KB Output is correct
6 Correct 63 ms 63608 KB Output is correct
7 Correct 63 ms 63564 KB Output is correct
8 Correct 64 ms 63652 KB Output is correct
9 Correct 71 ms 63756 KB Output is correct
10 Correct 64 ms 63688 KB Output is correct
11 Correct 64 ms 63608 KB Output is correct
12 Correct 64 ms 63736 KB Output is correct
13 Correct 64 ms 63736 KB Output is correct
14 Correct 64 ms 63608 KB Output is correct
15 Correct 63 ms 63664 KB Output is correct
16 Correct 64 ms 63736 KB Output is correct
17 Correct 66 ms 63864 KB Output is correct
18 Correct 64 ms 63608 KB Output is correct
19 Correct 67 ms 63892 KB Output is correct
20 Correct 66 ms 63736 KB Output is correct
21 Correct 64 ms 63864 KB Output is correct
22 Correct 67 ms 63992 KB Output is correct
23 Correct 67 ms 63992 KB Output is correct
24 Correct 67 ms 63928 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 63608 KB Output is correct
2 Correct 63 ms 63736 KB Output is correct
3 Correct 63 ms 63608 KB Output is correct
4 Correct 63 ms 63608 KB Output is correct
5 Correct 63 ms 63608 KB Output is correct
6 Correct 63 ms 63608 KB Output is correct
7 Correct 63 ms 63564 KB Output is correct
8 Correct 64 ms 63652 KB Output is correct
9 Correct 71 ms 63756 KB Output is correct
10 Correct 64 ms 63688 KB Output is correct
11 Correct 64 ms 63608 KB Output is correct
12 Correct 64 ms 63736 KB Output is correct
13 Correct 64 ms 63736 KB Output is correct
14 Correct 64 ms 63608 KB Output is correct
15 Correct 63 ms 63664 KB Output is correct
16 Correct 64 ms 63736 KB Output is correct
17 Correct 66 ms 63864 KB Output is correct
18 Correct 64 ms 63608 KB Output is correct
19 Correct 67 ms 63892 KB Output is correct
20 Correct 66 ms 63736 KB Output is correct
21 Correct 64 ms 63864 KB Output is correct
22 Correct 67 ms 63992 KB Output is correct
23 Correct 67 ms 63992 KB Output is correct
24 Correct 67 ms 63928 KB Output is correct
25 Correct 107 ms 65820 KB Output is correct
26 Correct 248 ms 69844 KB Output is correct
27 Correct 586 ms 75580 KB Output is correct
28 Correct 296 ms 67160 KB Output is correct
29 Correct 429 ms 74076 KB Output is correct
30 Correct 464 ms 68728 KB Output is correct
31 Correct 943 ms 82936 KB Output is correct
32 Correct 817 ms 78456 KB Output is correct
33 Correct 157 ms 70136 KB Output is correct
34 Correct 490 ms 79580 KB Output is correct
35 Correct 606 ms 95208 KB Output is correct
36 Execution timed out 1086 ms 98660 KB Time limit exceeded
37 Halted 0 ms 0 KB -