제출 #484612

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
484612		Alexandruabcde	Pinball (JOI14_pinball)	C++14	100 / 100	388 ms	29892 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

constexpr int NMAX = 1e5 + 5;
constexpr int VALMAX = 3 * NMAX + 5;
constexpr LL INF = 1e18;

int N, M;

int A[NMAX], B[NMAX], C[NMAX];
LL cost[NMAX];

LL AINT[4*VALMAX];

int vf = 0;
LL BestLeft[NMAX];
LL BestRight[NMAX];

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> M;

    for (int i = 1; i <= N; ++ i )
        cin >> A[i] >> B[i] >> C[i] >> cost[i];
}

void Normalize () {
    map <int, int> mp;

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

    int vf = 0;

    for (auto &it : mp)
        it.second = ++vf;

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

void ResetTree (int nod, int a, int b) {
    AINT[nod] = INF;
    if (a == b) return;

    int mij = (a + b) / 2;

    ResetTree(2*nod, a, mij);
    ResetTree(2*nod+1, mij+1, b);
}

void Update (int nod, int a, int b, int poz, LL val) {
    if (a == b) {
        AINT[nod] = min(AINT[nod], val);

        return;
    }

    int mij = (a + b) / 2;

    if (poz <= mij) Update(2*nod, a, mij, poz, val);
    else Update(2*nod+1, mij+1, b, poz, val);

    AINT[nod] = min(AINT[2*nod], AINT[2*nod+1]);
}

LL Query (int nod, int a, int b, int qa, int qb) {
    if (qa <= a && b <= qb) return AINT[nod];

    int mij = (a + b) / 2;
    LL ans_left = INF, ans_right = INF;

    if (qa <= mij) ans_left = Query(2*nod, a, mij, qa, qb);
    if (mij < qb) ans_right = Query(2*nod+1, mij+1, b, qa, qb);

    return min(ans_left, ans_right);
}

void Solve_Left () {
    ResetTree(1, 1, M);

    Update(1, 1, M, 1, 0);

    for (int i = 1; i <= N; ++ i ) {
        BestLeft[i] = Query(1, 1, M, A[i], B[i]);
        Update(1, 1, M, C[i], cost[i] + BestLeft[i]);
    }
}

void Solve_Right () {
    ResetTree(1, 1, M);

    Update(1, 1, M, M, 0);

    for (int i = 1; i <= N; ++ i ) {
        BestRight[i] = Query(1, 1, M, A[i], B[i]);
        Update(1, 1, M, C[i], cost[i] + BestRight[i]);
    }
}

void Solve () {
    Solve_Left();
    Solve_Right();

    LL ans = INF;
    for (int i = 1; i <= N; ++ i )
        ans = min(ans, BestLeft[i] + BestRight[i] + cost[i]);

    cout << (ans == INF ? -1 : ans) << '\n';
}

int main()
{
    Read();
    Normalize();
    Solve();

    return 0;
}

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