Submission #1251982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251982		mosesmayer	Pinball (JOI14_pinball)	C++20	0 / 100	2 ms	4928 KiB

pinball

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
typedef vector<int> vi;

template<class T> inline T re(){
    T N = 0; char c = getchar(); bool neg = 0;
    for (; c < '0' || c > '9'; c = getchar()) neg |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        N = (N<<3)+(N<<1) + c - '0';
    return neg ? -N : N;
}

const int MX = 1e5;
const LL LINF = 1e18;
int m, n;

struct device {
    int a, b, c, cost;
    device(int a = 0, int b = 0, int c = 0, int cost = 0):
        a(a), b(b), c(c), cost(cost) {}
} all[MX + 5];

map<int, int> mp;
void compress() {
    mp[1]; mp[n];
    for (int i = 1; i <= m; i++) {
        mp[all[i].a];
        mp[all[i].b];
        mp[all[i].c];
    }
    int cnt = 0;
    for (auto it = mp.begin(); it != mp.end(); it++) it -> se = ++cnt;
    n = mp[n];
    for (int i = 1; i <= m; i++) {
        all[i].a = mp[all[i].a];
        all[i].b = mp[all[i].b];
        all[i].c = mp[all[i].c];
    }
}

LL cost_kiri[MX + 5], cost_kanan[MX + 5]; // min cost to get to i.

struct SegTree {
    vector<LL> st;

    SegTree(int n = MX): st(n * 4 + 10) {}

    void build(int p = 1, int l = 1, int r = n) {
        if (l == r) return void(st[p] = LINF);
        int md = (l + r) >> 1;
        build(p << 1, l, md);
        build(p << 1 | 1, md + 1, r);
        st[p] = min(st[p << 1], st[p << 1 | 1]);
    }

    void upd(int pos, LL x, int p = 1, int l = 1, int r = n) {
        if (l == r) return void(st[p] = x);
        int md = (l + r) >> 1;
        if (pos <= md) upd(pos, x, p << 1, l, md);
        else upd(pos, x, p << 1 | 1, md + 1, r);
        st[p] = min(st[p << 1], st[p << 1 | 1]);
    }

    LL get(int i, int j, int p = 1, int l = 1, int r = n) {
        if (j < l || i > r) return LINF;
        if (i <= l && j >= r) return st[p];
        int md = (l + r) >> 1;
        return min(get(i, j, p << 1, l, md), get(i, j, p << 1 | 1, md + 1, r));
    }
} st;

int main() {
    m = re<int>(); n = re<int>();
    for (int i = 1, a, b, c, d; i <= m; i++) {
        a = re<int>();
        b = re<int>();
        c = re<int>();
        d = re<int>();
        all[i] = device(a, b, c, d);
    }
    compress();

    fill(cost_kiri, cost_kiri + m + 1, LINF);
    fill(cost_kanan, cost_kanan + m + 1, LINF);
    st = SegTree(m);

    // process left end
    st.build();
    st.upd(1, 0);
    for (int i = 1; i <= m; i++) {
        cost_kiri[i] = st.get(all[i].a, all[i].b) + all[i].cost;
        st.upd(all[i].c, cost_kiri[i]);
    }
    // process right end
    st.build();
    st.upd(n, 0);
    for (int i = 1; i <= m; i++) {
        cost_kanan[i] = st.get(all[i].a, all[i].b) + all[i].cost;
        st.upd(all[i].c, cost_kanan[i]);
    }

    LL ans = LINF;
    for (int i = 1; i <= m; i++) {
        if (cost_kiri[i] < LINF && cost_kanan[i] < LINF) {
            ans = min(ans, cost_kiri[i] + cost_kanan[i] - all[i].cost);
        }
    }
    printf("%lld\n", (ans >= LINF ? -1 : ans));
    return 0;
}

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