제출 #76345

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
76345		Vasiljko	Pinball (JOI14_pinball)	C++14	51 / 100	1074 ms	43856 KiB

pinball

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

typedef long long ll;
const ll MOD = 1e9+7;
const ll INF = 1e18+10;
const int N = 1e5+5;

ll n;
int m,original[3*N];
ll a[N],b[N],c[N],d[N],dpl[N],dpr[N];
map<ll,int>mp;
set<ll>s;

struct node{
    ll t;
    node *L,*R;
    node(){
        t=INF;
        L=nullptr;
        R=nullptr;
    }
}*root;

void Set(node *cur,ll ss,ll se,ll ind,ll val){
    if(ss==se){
        cur->t=min(cur->t,val);
        return;
    }
    ll mid=(ss+se)>>1LL;
    if(ind<=mid){
        if(cur->L==nullptr)cur->L=new node();
        Set(cur->L,ss,mid,ind,val);
        cur->t=min(cur->t,cur->L->t);
    }
    else{
        if(cur->R==nullptr)cur->R=new node();
        Set(cur->R,mid+1LL,se,ind,val);
        cur->t=min(cur->t,cur->R->t);
    }
}

ll Get(node *cur,ll ss,ll se,ll qs,ll qe){
    if(qs>se||qe<ss||ss>se)return INF;
    if(qs<=ss&&se<=qe)return cur->t;

    ll mid=(ss+se)>>1LL;

    if(cur->L==nullptr)cur->L=new node();
    if(cur->R==nullptr)cur->R=new node();

    return min(Get(cur->L,ss,mid,qs,qe),Get(cur->R,mid+1,se,qs,qe));
}


int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    root=new node();
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        s.insert(a[i]);
        s.insert(b[i]);
        s.insert(c[i]);
    }
    int cnt=0;
    for(auto e:s){
        mp[e]=++cnt;
        original[cnt]=e;
    }

    ll ans=2*INF;

    for(int i=1;i<=m;i++){
        if(a[i]==1){
            dpl[i]=d[i];
            Set(root,1,cnt,mp[c[i]],dpl[i]);
        }else{
            dpl[i]=INF;
            dpl[i]=min(dpl[i],d[i]+Get(root,1,cnt,mp[a[i]],mp[b[i]]));
            Set(root,1,cnt,mp[c[i]],dpl[i]);
        }
    }

    root = new node();
    for(int i=1;i<=m;i++){
        if(b[i]==n){
            dpr[i]=d[i];
            Set(root,1,cnt,mp[c[i]],dpr[i]);
        }else{
            dpr[i]=INF;
            dpr[i]=min(dpr[i],d[i]+Get(root,1,cnt,mp[a[i]],mp[b[i]]));
            Set(root,1,cnt,mp[c[i]],dpr[i]);
        }
    }

    for(int i=1;i<=m;i++)ans=min(ans,dpl[i]+dpr[i]-d[i]);
    if(ans==INF)ans=-1;

    cout<<ans;
    return 0;
}

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