Submission #481018

#	Time	Username	Problem	Language	Result	Execution time	Memory
481018		blue	Pinball (JOI14_pinball)	C++17	100 / 100	854 ms	90700 KiB

pinball

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

const long long INF = 1'000'000'000'000'000'000LL;

struct segtree
{
    int l;
    int r;
    long long mn = INF;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(l == r) return;
        int m = (l+r)/2;
        left = new segtree(l, m);
        right = new segtree(m+1, r);
    }

    void update(int I, long long V)
    {
        if(I < l || r < I) return;
        else if(l == r) mn = min(mn, V);
        else
        {
            left->update(I, V);
            right->update(I, V);
            mn = min(left->mn, right->mn);
        }
    }

    long long rangemin(int L, int R)
    {
        if(R < l || r < L) return INF;
        else if(L <= l && r <= R) return mn;
        else return min(left->rangemin(L, R), right->rangemin(L, R));
    }
};

long long op(long long q)
{
    if(q >= INF) q = -1;
    return q;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int M, N;
    cin >> M >> N;

    set<int> vals;
    map<int, int> newvals;

    vector<int> A(1+M), B(1+M), C(1+M);
    vector<long long> D(1+M);
    for(int i = 1; i <= M; i++)
    {
        cin >> A[i] >> B[i] >> C[i] >> D[i];

        vals.insert(A[i]);
        vals.insert(B[i]);
        vals.insert(C[i]);
    }

    vals.insert(1);
    vals.insert(N);

    int ct = 0;
    for(int v: vals)
    {
        ct++;
        newvals[v] = ct;
    }

    for(int i = 1; i <= M; i++)
    {
        A[i] = newvals[A[i]];
        B[i] = newvals[B[i]];
        C[i] = newvals[C[i]];
    }
    N = newvals[N];

    // cerr << N << '\n';
    // for(int i = 1; i <= M; i++) cerr << A[i] << ' ' << B[i] << ' ' << C[i] << '\n';
    //
    // cerr << "\n\n";


    segtree lft(1, N), rgt(1, N);
    lft.update(1, 0);
    rgt.update(N, 0);

    long long ans = INF;

    // cerr << "i = " << 0 << '\n';
    // for(int j = 1; j <= N; j++) cerr << op(lft.rangemin(j, j)) << ' ';
    // cerr << '\n';
    // for(int j = 1; j <= N; j++) cerr << op(rgt.rangemin(j, j)) << ' ';
    // cerr << '\n';
    // cerr << "ans = " << ans << '\n';

    for(int i = 1; i <= M; i++)
    {
        // cerr << "\n\n";
        // cerr << "i = " << i << '\n';

        long long LV = lft.rangemin(A[i], N);
        long long RV = rgt.rangemin(1, B[i]);

        ans = min(ans, LV + RV + D[i]);

        // cerr << lft.rangemin(C[i], C[i]) << ' ' << rgt.rangemin(C[i], C[i]) << '\n';


        // cerr << LV << ' ' << RV << ' ' << D[i] << '\n';

        lft.update(C[i], D[i] + LV);
        rgt.update(C[i], D[i] + RV);

        // for(int j = 1; j <= N; j++) cerr << op(lft.rangemin(j, j)) << ' ';
        // cerr << '\n';
        // for(int j = 1; j <= N; j++) cerr << op(rgt.rangemin(j, j)) << ' ';
        // cerr << '\n';
        // cerr << "ans = " << ans << '\n';
    }

    if(ans >= INF) ans = -1;
    cout << ans << '\n';
}

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