제출 #977314

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
977314		a_l_i_r_e_z_a	Pinball (JOI14_pinball)	C++17	100 / 100	137 ms	23756 KiB

pinball

// In the name of God
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC optimize("avx2")

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
// #define int long long
#define S second
#define F first
#define mp make_pair
#define smax(xyxy, yxy) (xyxy) = max((xyxy), (yxy))
#define smin(xyxy, yxy) (xyxy) = min((xyxy), (yxy))
#define all(xyxy) (xyxy).begin(), (xyxy).end()
#define len(xyxy) ((int)(xyxy).size())

const int maxn = 1e5 + 5;
const ll inf = 1e15 + 7;
int n, m, a[maxn], b[maxn], c[maxn], d[maxn];
vector<int> vec;
pll node[maxn * 4 * 3];

void build(int l = 0, int r = n, int id = 1){
    if(l == r - 1){
        if(l == 0) node[id] = mp(0, inf);
        else if(l == n - 1) node[id] = mp(inf, 0);
        else node[id] = mp(inf, inf);
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, id * 2);
    build(mid, r, id * 2 + 1);
    node[id] = mp(min(node[id * 2].F, node[id * 2 + 1].F), min(node[id * 2].S, node[id * 2 + 1].S));
}

pll get(int s, int f, int l = 0, int r = n, int id = 1){
    if(s <= l && r <= f) return node[id];
    if(f <= l || r <= s) return mp(inf, inf);
    int mid = (l + r) / 2;
    pll x = get(s, f, l, mid, id * 2), y = get(s, f, mid, r, id * 2 + 1);
    return mp(min(x.F, y.F), min(x.S, y.S));
}

void upd(int p, pll x, int l = 0, int r = n, int id = 1){
    if(l == r - 1){
        smin(node[id].F, x.F);
        smin(node[id].S, x.S);
        return;
    }
    int mid = (l + r) / 2;
    if(p < mid) upd(p, x, l, mid, id * 2);
    else upd(p, x, mid, r, id * 2 + 1);
    node[id] = mp(min(node[id * 2].F, node[id * 2 + 1].F), min(node[id * 2].S, node[id * 2 + 1].S));
}

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> m >> n;
    ll mx = 0, mn = inf;
    for(int i = 0; i < m; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        vec.pb(a[i]);
        vec.pb(c[i]);
        vec.pb(b[i]);
        smin(mn, 1ll * a[i]);
        smax(mx, 1ll * b[i]);
    }
    if(mx != n || mn != 1){
        cout << -1 << '\n';
        return 0;
    }
    sort(all(vec));
    vec.resize(unique(all(vec)) - vec.begin());
    n = vec.size();
    if(n == 1){
        cout << 0 << '\n';
        return 0;
    }
    for(int i = 0; i < m; i++){
        a[i] = lower_bound(all(vec), a[i]) - vec.begin();
        b[i] = lower_bound(all(vec), b[i]) - vec.begin();
        c[i] = lower_bound(all(vec), c[i]) - vec.begin();
    }
    build();
    ll ans = inf;
    for(int i = 0; i < m; i++){
        pll x = get(a[i], b[i] + 1);
        smin(ans, d[i] + x.F + x.S);
        upd(c[i], mp(x.F + d[i], x.S + d[i]));
    }
    if(ans < inf) cout << ans << '\n';
    else cout << -1 << '\n';

    return 0;
}

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