Submission #1180334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180334		chikien2009	Pinball (JOI14_pinball)	C++20	51 / 100	114 ms	21832 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

class SEGMENT_TREE
{
private:
    int tree_size;
    vector<long long> tree;

    inline void Update(int ind, int l, int r, int x, long long v)
    {
        if (r < x || x < l)
        {
            return;
        }
        if (l == r)
        {
            tree[ind] = min(tree[ind], v);
            return;
        }
        int m = (l + r) >> 1;
        Update(ind << 1, l, m, x, v);
        Update(ind << 1 | 1, m + 1, r, x, v);
        tree[ind] = min(tree[ind << 1], tree[ind << 1 | 1]);
    }
    inline long long Get(int ind, int l, int r, int x, int y)
    {
        if (r < x || y < l)
        {
            return 1e18;
        }
        if (x <= l && r <= y)
        {
            return tree[ind];
        }
        int m = (l + r) >> 1;
        return min(Get(ind << 1, l, m, x, y), Get(ind << 1 | 1, m + 1, r, x, y));
    }

public:
    inline SEGMENT_TREE(int new_size)
    {
        tree_size = new_size;
        tree.clear();
        tree.resize(tree_size << 2, 1e18);
    }
    inline void Update(int x, long long v)
    {
        Update(1, 1, tree_size, x, v);
    }
    inline long long Get(int x, int y)
    {
        return Get(1, 1, tree_size, x, y);
    }
} st1(300005), st2(300005);

int n, m, b[300000], k, d[100000];
array<int, 3> a[100000];
long long res = 1e18, t1, t2;

int main()
{
    setup();

    cin >> m >> n;
    for (int i = 0; i < m; ++i)
    {
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> d[i];
        b[i * 3] = a[i][0];
        b[i * 3 + 1] = a[i][1];
        b[i * 3 + 2] = a[i][2];
    }
    b[3 * m] = 1;
    b[3 * m + 1] = n;
    sort(b, b + 3 * m + 2);
    k = unique(b, b + 3 * m + 2) - b;
    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            a[i][j] = lower_bound(b, b + k, a[i][j]) - b + 1;
        }
    }
    st1.Update(1, 0);
    st2.Update(k, 0);
    for (int i = 0; i < m; ++i)
    {
        t1 = st1.Get(a[i][0], a[i][1]);
        t2 = st2.Get(a[i][0], a[i][1]);
        res = min(res, t1 + t2 + d[i]);
        st1.Update(a[i][2], t1 + d[i]);
        st2.Update(a[i][2], t2 + d[i]);
    }
    cout << (res == 1e18 ? -1 : res);
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 49