oj.uz

Submission #481012

# Submission time Handle Problem Language Result Execution time Memory
481012 2021-10-19T07:52:04 Z blue Pinball (JOI14_pinball) C++17
11 / 100
 360 ms 800 KB 
#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++)
    {
        long long LV = lft.rangemin(A[i], C[i]);
        if(LV < INF)
            lft.update(C[i], D[i] + LV);

        long long RV = rgt.rangemin(C[i], B[i]);
        if(RV < INF)
            rgt.update(C[i], D[i] + RV);

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

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

        cerr << "\n\n";

        cerr << "i = " << i << '\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';
    }



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

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 89 ms 496 KB Output is correct
10 Correct 222 ms 704 KB Output is correct
11 Incorrect 360 ms 800 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 89 ms 496 KB Output is correct
10 Correct 222 ms 704 KB Output is correct
11 Incorrect 360 ms 800 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 3 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 89 ms 496 KB Output is correct
10 Correct 222 ms 704 KB Output is correct
11 Incorrect 360 ms 800 KB Output isn't correct
12 Halted 0 ms 0 KB -