Submission #900635

#	Time	Username	Problem	Language	Result	Execution time	Memory
900635		imarn	Pinball (JOI14_pinball)	C++14	100 / 100	129 ms	16988 KiB

pinball

#include<bits/stdc++.h>
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=3e5+5;
struct segment{
    ll a[2*N];
    void build(){
        for(int i=0;i<2*N;i++)a[i]=1e16;
    }
    void upd(int i,ll amt,int sz){
        i+=sz;a[i]=min(a[i],amt);
        for(i>>=1;i;i>>=1)a[i]=min(a[2*i],a[2*i+1]);
    }
    ll qr(int l,int r,int sz,ll res=1e16){
        for(l+=sz,r+=sz;l<r;l>>=1,r>>=1){
            if(l&1)res=min(res,a[l++]);
            if(r&1)res=min(res,a[--r]);
        }return res;
    }
}t[2];
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int m,n;cin>>m>>n;ll ans=1e15;
    vector<int> com;com.pb(1);com.pb(n);
    int a[m],b[m],c[m];ll d[m];
    for(int i=0;i<m;i++)cin>>a[i]>>b[i]>>c[i]>>d[i],com.pb(a[i]),com.pb(b[i]),com.pb(c[i]);
    sort(all(com));com.erase(unique(all(com)),com.end());t[0].build();t[1].build();int sz=com.size();
    for(int i=0;i<m;i++){
        int ax=lower_bound(all(com),a[i])-com.begin();
        int bx=lower_bound(all(com),b[i])-com.begin();
        int cx=lower_bound(all(com),c[i])-com.begin();
        ll resl=1e15,resr=1e15;
        if(a[i]==1)resl=0;
        if(b[i]==n)resr=0;
        resl=min(resl,t[0].qr(ax,bx+1,sz));
        resr=min(resr,t[1].qr(ax,bx+1,sz));
        ans=min(ans,resl+resr+d[i]);
        t[0].upd(cx,resl+d[i],sz);t[1].upd(cx,resr+d[i],sz);
    }cout<<(ans==1e15?-1:ans);
}

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