Submission #1086046

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086046		Icelast	Pinball (JOI14_pinball)	C++17	100 / 100	198 ms	30944 KiB

pinball

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
struct device{
    ll l, r, m, c, id;
};
struct normalize{
    vector<ll> poi, pot;
    void add(ll x){
        poi.push_back(x);
    }
    void start(){
        sort(poi.begin(), poi.end());
        pot.push_back(poi[0]);
        for(int i = 1; i < (int)poi.size(); i++){
            if(poi[i] != poi[i-1]){
                pot.push_back(poi[i]);
            }
        }
    }
    int encode(ll x){
        return lower_bound(pot.begin(), pot.end(), x) - pot.begin()+1;
    }
};
struct SegmentTree{
    struct Node{
        ll mn = INF;
    };
    vector<Node> T;
    int n, N;
    SegmentTree(int n) : n(n){
        N = 1;
        while(N < n) N*=2;
        T.resize(N*2+1);
    };
    void upd(int i, ll x){
        auto upd = [&](auto upd, int node, int low, int high, int i, ll x) -> void{
            if(low == high){
                T[node].mn = min(T[node].mn, x);
                return;
            }
            int mid = (low+high)/2;
            if(i <= mid){
                upd(upd, node*2, low, mid, i, x);
            }else{
                upd(upd, node*2+1, mid+1, high, i, x);
            }
            T[node].mn = min(T[node*2].mn, T[node*2+1].mn);
        };
        upd(upd, 1, 1, N, i, x);
    }
    ll get_min(int l, int r){
        auto get_min = [&](auto get_min, int node, int low, int high, int l, int r) -> ll{
            if(low > r || l > high) return INF;
            if(low >= l && r >= high) return T[node].mn;
            int mid = (low+high)/2;
            return min(get_min(get_min, node*2, low, mid, l, r), get_min(get_min, node*2+1, mid+1, high, l, r));
        };
        return get_min(get_min, 1, 1, N, l, r);
    }
};
void solve(){
    int n, m;
    cin >> n >> m;
    vector<device> a(n+1);
    for(int i = 1; i <= n; i++){
        cin >> a[i].l >> a[i].r >> a[i].m >> a[i].c;
        a[i].id = i;
    }
    normalize norm;
    norm.add(1);
    norm.add(m);
    for(int i = 1; i <= n; i++){
        norm.add(a[i].l);
        norm.add(a[i].r);
        norm.add(a[i].m);
    }
    norm.start();
    m = norm.encode(m);
    for(int i = 1; i <= n; i++){
        a[i].l = norm.encode(a[i].l);
        a[i].r = norm.encode(a[i].r);
        a[i].m = norm.encode(a[i].m);
    }

    int N = 3*n+2;
    SegmentTree Tl(N+1), Tr(N+1);
    Tl.upd(1, 0);
    Tr.upd(m, 0);
    vector<ll> dpl(n+1, INF), dpr(n+1, INF);
    for(int i = 1; i <= n; i++){
        dpl[i] = Tl.get_min(a[i].l, a[i].r)+a[i].c;
        Tl.upd(a[i].m, dpl[i]);
        dpr[i] = Tr.get_min(a[i].l, a[i].r)+a[i].c;
        Tr.upd(a[i].m, dpr[i]);
    }
    ll ans = INF;
    for(int i = 1; i <= n; i++){
        ans = min(ans, dpl[i]+dpr[i]-a[i].c);
    }
    if(ans == INF) ans = -1;
    cout << ans;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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