Submission #955196

#	Time	Username	Problem	Language	Result	Execution time	Memory
955196		sandry24	Pinball (JOI14_pinball)	C++17	100 / 100	243 ms	32640 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
#define pb push_back
#define mp make_pair
#define f first
#define s second

const ll maxn = 1e5+5, INF = 1e15;
vi a(maxn), b(maxn), c(maxn), d(maxn), coords; 
vector<vector<ll>> seg(2, vector<ll>(12*maxn, INF));
vector<ll> lm(3*maxn, INF), rm(3*maxn, INF);

ll query(int v, int tl, int tr, int l, int r, int idx){
    if(l > r)
        return 1e16;
    if(tl == l && tr == r)
        return seg[idx][v];
    int tm = (tl + tr) / 2;
    return min(query(v*2, tl, tm, l, min(tm, r), idx), 
        query(v*2+1, tm+1, tr, max(tm+1, l), r, idx));
}

void upd(int v, int tl, int tr, int pos, ll val, int idx){
    if(tl == tr){
        seg[idx][v] = val;
    } else {
        int tm = (tl + tr) / 2;
        if(pos <= tm)
            upd(v*2, tl, tm, pos, val, idx);
        else
            upd(v*2+1, tm+1, tr, pos, val, idx);
        seg[idx][v] = min(seg[idx][v*2], seg[idx][v*2+1]);
    }
}

void solve(){
    int n, m;
    cin >> n >> m;
    coords.pb(1); coords.pb(m);
    for(int i = 0; i < n; i++){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        coords.pb(a[i]);
        coords.pb(b[i]);
        coords.pb(c[i]);
    }
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    int sz = coords.size();
    for(int i = 0; i < n; i++){
        a[i] = lower_bound(coords.begin(), coords.end(), a[i]) - coords.begin();
        b[i] = lower_bound(coords.begin(), coords.end(), b[i]) - coords.begin();
        c[i] = lower_bound(coords.begin(), coords.end(), c[i]) - coords.begin();
    }
    upd(1, 0, sz-1, 0, 0, 0); lm[0] = 0;
    upd(1, 0, sz-1, sz-1, 0, 1); rm[sz-1] = 0;
    ll ans = 1e15;
    for(int i = 0; i < n; i++){
        ll lf = query(1, 0, sz-1, a[i], b[i], 0);
        ll rt = query(1, 0, sz-1, a[i], b[i], 1);
        ans = min(ans, lf + rt + d[i]);
        lm[c[i]] = min(lm[c[i]], lf + d[i]);
        rm[c[i]] = min(rm[c[i]], rt + d[i]);
        upd(1, 0, sz-1, c[i], lm[c[i]], 0);
        upd(1, 0, sz-1, c[i], rm[c[i]], 1);
    }
    if(ans == 1e15)
        cout << -1 << '\n';
    else
        cout << ans << '\n';
} 
 
int main(){
    // freopen("monede.in", "r", stdin);
    // freopen("monede.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

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