Submission #146650

#	Time	Username	Problem	Language	Result	Execution time	Memory
146650		brcode	Pinball (JOI14_pinball)	C++14	100 / 100	913 ms	38372 KiB

pinball

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
const long long MAXN = 1e6+5;
long long a[MAXN];
long long b[MAXN];
long long ans = 1e17;
long long c[MAXN];
long long d[MAXN];
map<long long,long long> compress;
long long dp[MAXN];
long long dp2[MAXN];
long long seg[12*MAXN];
vector<long long> v1;
void build(long long curr,long long l,long long r){
   
    if(l==r){
        
        seg[curr] = 1e17;
        return;
    }
    long long mid = (l+r)/2;
    build(2*curr,l,mid);
    build(2*curr+1,mid+1,r);
    seg[curr] = min(seg[2*curr],seg[2*curr+1]);
    //cout<<seg[curr]<<endl;
}
long long query(long long curr,long long tl,long long tr,long long l,long long r){
    if(l>tr||r<tl){
        return 1e17;
    }
    if(tl == 5 && tr == 12){
     //   cout<<seg[curr]<<" "<<l<<" "<<r<<endl;
    }
    if(l>=tl && r<=tr){
        return seg[curr];
    }
    long long mid = (l+r)/2;
    return min(query(2*curr,tl,tr,l,mid),query(2*curr+1,tl,tr,mid+1,r));
}
void update(long long curr,long long l,long long r,long long pos,long long val){
    if(l==r){
        seg[curr] = min(seg[curr],val);
        
        return;
    }
    
    long long mid = (l+r)/2;
    if(pos<=mid){
        update(2*curr,l,mid,pos,val);
    }else{
        update(2*curr+1,mid+1,r,pos,val);
    }
    seg[curr] = min(seg[2*curr],seg[2*curr+1]);
}
int main(){
  ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n,m;
    cin>>n>>m;
    
    for(long long i=1;i<=n;i++){
        cin>>a[i]>>b[i]>>c[i]>>d[i];    
        v1.push_back(a[i]);
        v1.push_back(b[i]);
        v1.push_back(c[i]);
    }
    sort(v1.begin(),v1.end());
    for(long long i=1;i<=3*n;i++){
        compress[v1[i-1]] = i;
    }
    int newcols = v1.size()+1;
   // cout<<newcols<<endl;
        for(long long i=1;i<=n;i++){
        dp[i] = 1e17;
        dp2[i] = 1e17;
    }
    build(1,1,newcols);
    for(long long i=1;i<=n;i++){
        if(a[i] == 1){
            dp[i] = d[i];
        }
        
        dp[i] = min(dp[i],d[i] + query(1,compress[a[i]],compress[b[i]],1,newcols));
        
        update(1,1,newcols,compress[c[i]],dp[i]);
       // cout<<dp[i]<<" "<<compress[b[i]]<<" "<<compress[c[i]]<<endl;
    }
    build(1,1,newcols);
    for(long long i=1;i<=n;i++){
        if(b[i] == m){
            dp2[i] = d[i];
        }
        dp2[i] = min(dp2[i],d[i] + query(1,compress[a[i]],compress[b[i]],1,newcols));
        update(1,1,newcols,compress[c[i]],dp2[i]);
//cout<<<<" "<<dp2[i]<<endl;
    }
    for(long long i=1;i<=n;i++){
        ans = min(ans,dp[i]+dp2[i]-d[i]);
       // cout<<i<<" "<<dp2[i]<<endl;
    }
    if(ans>=1e17){
        cout<<-1<<endl;
        return 0;
    }
    cout<<ans<<endl;
}

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