oj.uz

Submission #1086044

# Submission time Handle Problem Language Result Execution time Memory
1086044 2024-09-09T11:26:37 Z Icelast Pinball (JOI14_pinball) C++17
0 / 100
 1 ms 452 KB 
#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(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+1;
    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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 452 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 452 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 452 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 360 KB Output is correct
4 Correct 0 ms 452 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Incorrect 0 ms 348 KB Output isn't correct
8 Halted 0 ms 0 KB -