Submission #501910

#	Time	Username	Problem	Language	Result	Execution time	Memory
501910		RGBB	Pinball (JOI14_pinball)	C++14	100 / 100	533 ms	61832 KiB

pinball

#include <iostream>
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int MAXN=1e5;
int n,t,s,inp[MAXN][4];
ll ldp[MAXN],rdp[MAXN],mdp[MAXN],lseg[1<<20],rseg[1<<20],mseg[1<<20];
set<int>sorted;
gp_hash_table<int,int>cmp;
ll bestLeft(int a,int b,int c,int be,int en){
    if(a>en||b<be)return LLONG_MAX;
    if(a>=be&&b<=en)return lseg[c];
    return min(bestLeft(a,(a+b)/2,2*c+1,be,en),bestLeft((a+b)/2+1,b,2*c+2,be,en));
}
ll bestRight(int a,int b,int c,int be,int en){
    if(a>en||b<be)return LLONG_MAX;
    if(a>=be&&b<=en)return rseg[c];
    return min(bestRight(a,(a+b)/2,2*c+1,be,en),bestRight((a+b)/2+1,b,2*c+2,be,en));
}
ll bestMid(int a,int b,int c,int be,int en){
    if(a>en||b<be)return LLONG_MAX;
    if(a>=be&&b<=en)return mseg[c];
    return min(bestMid(a,(a+b)/2,2*c+1,be,en),bestMid((a+b)/2+1,b,2*c+2,be,en));
}
void leftInsert(int a,int b,int c,int p,ll v){
    if(a>p||b<p)return;
    if(a==b){
        lseg[c]=min(lseg[c],v);
        return;
    }
    leftInsert(a,(a+b)/2,2*c+1,p,v);
    leftInsert((a+b)/2+1,b,2*c+2,p,v);
    lseg[c]=min(lseg[2*c+1],lseg[2*c+2]);
}
void rightInsert(int a,int b,int c,int p,ll v){
    if(a>p||b<p)return;
    if(a==b){
        rseg[c]=min(rseg[c],v);
        return;
    }
    rightInsert(a,(a+b)/2,2*c+1,p,v);
    rightInsert((a+b)/2+1,b,2*c+2,p,v);
    rseg[c]=min(rseg[2*c+1],rseg[2*c+2]);
}
void midInsert(int a,int b,int c,int p,ll v){
    if(a>p||b<p)return;
    if(a==b){
        mseg[c]=min(mseg[c],v);
        return;
    }
    midInsert(a,(a+b)/2,2*c+1,p,v);
    midInsert((a+b)/2+1,b,2*c+2,p,v);
    mseg[c]=min(mseg[2*c+1],mseg[2*c+2]);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>t;
    for(int i=0;i<n;i++){
        cin>>inp[i][0]>>inp[i][1]>>inp[i][2]>>inp[i][3];
        sorted.insert(inp[i][0]);
        sorted.insert(inp[i][1]);
        sorted.insert(inp[i][2]);
    }
    s=0;
    for(auto&i:sorted)cmp[i]=s++;
    for(int i=0;i<(1<<20);i++){
        lseg[i]=LLONG_MAX;
        rseg[i]=LLONG_MAX;
        mseg[i]=LLONG_MAX;
    }
    for(int i=0;i<n;i++){
        ll l=bestLeft(0,s-1,0,cmp[inp[i][0]],cmp[inp[i][1]]);
        ll r=bestRight(0,s-1,0,cmp[inp[i][0]],cmp[inp[i][1]]);
        ll m=bestMid(0,s-1,0,cmp[inp[i][0]],cmp[inp[i][1]]);
        if(inp[i][0]==1)l=0;
        if(inp[i][1]==t)r=0;
        ldp[i]=(l!=LLONG_MAX?l+inp[i][3]:LLONG_MAX);
        rdp[i]=(r!=LLONG_MAX?r+inp[i][3]:LLONG_MAX);
        mdp[i]=(m!=LLONG_MAX?m+inp[i][3]:LLONG_MAX);
        if(l!=LLONG_MAX&&r!=LLONG_MAX)mdp[i]=min(mdp[i],l+r+inp[i][3]);
        leftInsert(0,s-1,0,cmp[inp[i][2]],ldp[i]);
        rightInsert(0,s-1,0,cmp[inp[i][2]],rdp[i]);
        midInsert(0,s-1,0,cmp[inp[i][2]],mdp[i]);
    }
    ll outp=LLONG_MAX;
    for(int i=0;i<n;i++)outp=min(outp,mdp[i]);
    cout<<(outp!=LLONG_MAX?outp:-1)<<"\n";
}

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