Submission #416068

#	Time	Username	Problem	Language	Result	Execution time	Memory
416068		Lobo	Pinball (JOI14_pinball)	C++17	100 / 100	469 ms	35572 KiB

pinball

#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = 1e18;
const int INFii = 1e9;
typedef long long ll;
typedef int ii;
typedef double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back

#define maxn 110000
//LEMBRAR DE MUDAR

ll n, m, dp1[5*maxn], dp2[5*maxn], tr[20*maxn][2];
ll a[maxn], b[maxn], c[maxn], d[maxn];

void build(ll no, ll l, ll r) {
    tr[no][0] = tr[no][1] = INFll;

    ll mid = (l+r)/2;
    ll f1 = 2*no;
    ll f2 = 2*no+1;

    if(l == r) return;
    build(f1,l,mid);
    build(f2,mid+1,r);
}

//seg de minimo
void att(ll no, ll l, ll r, ll pos, ll val, ll p) {
    if(l > pos || r < pos) return;
    else if(l == r) {
        tr[no][p] = min(val,tr[no][p]);
    }
    else {
        ll mid = (l+r)/2;
        ll f1 = 2*no;
        ll f2 = 2*no+1;
        
        att(f1,l,mid,pos,val,p);
        att(f2,mid+1,r,pos,val,p);
        tr[no][p] = min(tr[f1][p],tr[f2][p]);
    }
}

ll query(ll no, ll l, ll r, ll L, ll R, ll p) {
    if(l > R || r < L) return INFll;
    else if(l >= L && r <= R) {
        return tr[no][p];
    }
    else {
        ll mid = (l+r)/2;
        ll f1 = 2*no;
        ll f2 = 2*no+1;
        
        return min(query(f1,l,mid,L,R,p),query(f2,mid+1,r,L,R,p));
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);
    //freopen("____.out", "w", stdout);

    cin >> m >> n;

    vector<ll> comp;
    for(ii i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];

        if(a[i]-1 != 0) comp.pb(a[i]-1);
        comp.pb(a[i]);
        comp.pb(c[i]);
        comp.pb(b[i]);
        if(b[i]+1 != n+1) comp.pb(b[i]+1);
        
    }

    sort(comp.begin(),comp.end());
    comp.erase(unique(comp.begin(),comp.end()),comp.end());

    n = comp.size();
    build(1,1,n);
    for(ll i = 1; i <= n; i++) {
        dp1[i] = dp2[i] = INFll;
    }

    dp1[1] = 0;
    att(1,1,n,1,0,0);
    dp2[n] = 0;
    att(1,1,n,n,0,1);

    for(ll i = 1; i <= m; i++) {
        a[i] = upper_bound(comp.begin(),comp.end(),a[i]) - comp.begin();
        b[i] = upper_bound(comp.begin(),comp.end(),b[i]) - comp.begin();
        c[i] = upper_bound(comp.begin(),comp.end(),c[i]) - comp.begin();
    }

    ll ans = INFll;
    for(ll i = 1; i <= m; i++) {
        ll mn1 = query(1,1,n,a[i],b[i],0);
        dp1[c[i]] = min(dp1[c[i]], mn1+d[i]);
        att(1,1,n,c[i],mn1+d[i],0);

        ll mn2 = query(1,1,n,a[i],b[i],1);
        dp2[c[i]] = min(dp1[c[i]], mn2+d[i]);
        att(1,1,n,c[i],mn2+d[i],1);

        ans = min(ans, mn1+mn2+d[i]);
    }

    if(ans >= (ll) 1e16) cout << -1 << endl;
    else cout << ans << endl;
    return 0;

}

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