oj.uz

Submission #581581

# Submission time Handle Problem Language Result Execution time Memory
581581 2022-06-22T19:06:20 Z Vanilla Pinball (JOI14_pinball) C++17
100 / 100
 427 ms 35924 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long int64;
const int maxn = 1e5 + 2;
int64 a[maxn], b[maxn], c[maxn], cost[maxn];
vector <int64> coord;
int64 n,m;

template <class T> class segtree {

    private:
        vector <T> tree;
        int n, il, ir;
        
        void build (vector <T> &a, int node, int l, int r) {
            if (l == r) {
                tree[node] = a[l];
                return;
            }
            int m = (l + r) / 2;
            build(a, node * 2, l, m);
            build(a, node * 2 + 1, m + 1, r);
            tree[node] = calc(tree[node * 2], tree[node * 2 + 1]);
        }
        
        T __query (int node, int l, int r) {
            if (il <= l && r <= ir) return tree[node];
            T s1 = 1e15, s2 = 1e15;
            int m = (l + r) / 2;
            if (il <= m) {
                s1 = __query(node * 2, l, m);
            }
            if (m + 1 <= ir) {
                s2 = __query(node * 2 + 1, m + 1, r);
            }
            return calc(s1, s2);
        }

        void __update (int node, int l, int r, int& px, T& val) {
            if (l == r) {
                tree[node] = min(tree[node], val);
                return;
            }
            int m = (l + r) / 2;
            if (px <= m) {
                __update(node * 2, l, m, px, val);
            }
            else {
                __update(node * 2 + 1, m + 1, r, px, val);
            }
            tree[node] = calc(tree[node * 2], tree[node * 2 + 1]);
        }

    public: 
        segtree (int n) {
            this->n = n;
            tree.resize(n * 4);
            for (int i = 0; i < n * 4; i++){
                tree[i] = 1e15;
            }
        }

        T query (int l, int r) {
            il = l, ir = r;
            return __query(1, 0, n);
        }

        void update (int pos, T val) {
            return __update(1, 0, n, pos, val);
        }

        T calc (T a, T b) {
            return min(a, b);
        }

};

segtree <int64> mnl (maxn * 4);
segtree <int64> mnr (maxn * 4);
 
 
int main() {
    cin >> n >> m;
    bool f1 = 0, f2 = 0;
    for (int i = 0; i < n; i++){
        cin >> a[i] >> b[i] >> c[i] >> cost[i];
        if (a[i] == 1) f1 = 1;
        if (b[i] == m) f2 = 1;
        coord.push_back(a[i]);
        coord.push_back(b[i]);
        coord.push_back(c[i]);
    }
    if (!f1 || !f2){
        cout << -1;
        return 0;
    }
    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());
    m = 0;
    for (int i = 0; i < n; i++){
        a[i] = lower_bound(coord.begin(), coord.end(), a[i]) - coord.begin();
        b[i] = lower_bound(coord.begin(), coord.end(), b[i]) - coord.begin();
        c[i] = lower_bound(coord.begin(), coord.end(), c[i]) - coord.begin();
        m = max(m, b[i]);
    }
    int64 rs = 1e15;
    mnl.update(0, 0);
    mnr.update(m, 0);
    for (int i = 0; i < n; i++){
        rs = min(rs, mnl.query(a[i], b[i]) + mnr.query(a[i], b[i]) + cost[i]);
        mnl.update(c[i], mnl.query(a[i], b[i]) + cost[i]);
        mnr.update(c[i], mnr.query(a[i], b[i]) + cost[i]);
    }
 
    cout << (rs >= 1e15 ? -1: rs);
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25300 KB Output is correct
2 Correct 14 ms 25300 KB Output is correct
3 Correct 14 ms 25300 KB Output is correct
4 Correct 14 ms 25308 KB Output is correct
5 Correct 15 ms 25344 KB Output is correct
6 Correct 14 ms 25384 KB Output is correct
7 Correct 16 ms 25372 KB Output is correct
8 Correct 15 ms 25376 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25300 KB Output is correct
2 Correct 14 ms 25300 KB Output is correct
3 Correct 14 ms 25300 KB Output is correct
4 Correct 14 ms 25308 KB Output is correct
5 Correct 15 ms 25344 KB Output is correct
6 Correct 14 ms 25384 KB Output is correct
7 Correct 16 ms 25372 KB Output is correct
8 Correct 15 ms 25376 KB Output is correct
9 Correct 15 ms 25360 KB Output is correct
10 Correct 14 ms 25364 KB Output is correct
11 Correct 16 ms 25380 KB Output is correct
12 Correct 14 ms 25372 KB Output is correct
13 Correct 16 ms 25300 KB Output is correct
14 Correct 15 ms 25384 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25300 KB Output is correct
2 Correct 14 ms 25300 KB Output is correct
3 Correct 14 ms 25300 KB Output is correct
4 Correct 14 ms 25308 KB Output is correct
5 Correct 15 ms 25344 KB Output is correct
6 Correct 14 ms 25384 KB Output is correct
7 Correct 16 ms 25372 KB Output is correct
8 Correct 15 ms 25376 KB Output is correct
9 Correct 15 ms 25360 KB Output is correct
10 Correct 14 ms 25364 KB Output is correct
11 Correct 16 ms 25380 KB Output is correct
12 Correct 14 ms 25372 KB Output is correct
13 Correct 16 ms 25300 KB Output is correct
14 Correct 15 ms 25384 KB Output is correct
15 Correct 15 ms 25308 KB Output is correct
16 Correct 16 ms 25300 KB Output is correct
17 Correct 18 ms 25396 KB Output is correct
18 Correct 17 ms 25428 KB Output is correct
19 Correct 15 ms 25616 KB Output is correct
20 Correct 17 ms 25428 KB Output is correct
21 Correct 16 ms 25428 KB Output is correct
22 Correct 17 ms 25428 KB Output is correct
23 Correct 16 ms 25504 KB Output is correct
24 Correct 18 ms 25524 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 25300 KB Output is correct
2 Correct 14 ms 25300 KB Output is correct
3 Correct 14 ms 25300 KB Output is correct
4 Correct 14 ms 25308 KB Output is correct
5 Correct 15 ms 25344 KB Output is correct
6 Correct 14 ms 25384 KB Output is correct
7 Correct 16 ms 25372 KB Output is correct
8 Correct 15 ms 25376 KB Output is correct
9 Correct 15 ms 25360 KB Output is correct
10 Correct 14 ms 25364 KB Output is correct
11 Correct 16 ms 25380 KB Output is correct
12 Correct 14 ms 25372 KB Output is correct
13 Correct 16 ms 25300 KB Output is correct
14 Correct 15 ms 25384 KB Output is correct
15 Correct 15 ms 25308 KB Output is correct
16 Correct 16 ms 25300 KB Output is correct
17 Correct 18 ms 25396 KB Output is correct
18 Correct 17 ms 25428 KB Output is correct
19 Correct 15 ms 25616 KB Output is correct
20 Correct 17 ms 25428 KB Output is correct
21 Correct 16 ms 25428 KB Output is correct
22 Correct 17 ms 25428 KB Output is correct
23 Correct 16 ms 25504 KB Output is correct
24 Correct 18 ms 25524 KB Output is correct
25 Correct 44 ms 26280 KB Output is correct
26 Correct 97 ms 27988 KB Output is correct
27 Correct 261 ms 31864 KB Output is correct
28 Correct 295 ms 35864 KB Output is correct
29 Correct 211 ms 30800 KB Output is correct
30 Correct 369 ms 35840 KB Output is correct
31 Correct 419 ms 35880 KB Output is correct
32 Correct 384 ms 35880 KB Output is correct
33 Correct 67 ms 27212 KB Output is correct
34 Correct 196 ms 30736 KB Output is correct
35 Correct 274 ms 35912 KB Output is correct
36 Correct 427 ms 35844 KB Output is correct
37 Correct 368 ms 35820 KB Output is correct
38 Correct 350 ms 35924 KB Output is correct