Submission #1206855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206855		Newtonabc	Pinball (JOI14_pinball)	C++20	100 / 100	184 ms	20412 KiB

pinball

#include<bits/stdc++.h>
#define pii pair<int,int>
#define pil pair<int,long long>
using namespace std;
const int N=1<<20;
const int M=1e5+10;
vector<int> con;
int fd(int x){
    int ind=lower_bound(con.begin(),con.end(),x)-con.begin()+1;
    return ind;
}
struct stree{
    vector<long long> s;
    void init(){
        s.resize(N+10,LLONG_MAX);
    }
    void update(int l,int r,int idx,int a,long long b){
        if(a<l || a>r) return;
        if(l==r){
            s[idx]=min(s[idx],b);
            return;
        }
        int m=(l+r)/2;
        update(l,m,idx*2,a,b);
        update(m+1,r,idx*2+1,a,b);
        s[idx]=min(s[idx*2],s[idx*2+1]);
    }
    long long query(int l,int r,int idx,int a,int b){
        if(b<l || a>r) return LLONG_MAX;
        if(a<=l && b>=r) return s[idx];
        int m=(l+r)/2;
        return min(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
    }
};
pair<pii,pil> arr[M];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n >>m;
    for(int i=1;i<=n;i++){
        int a,b,c;
        long long d;
        cin>>a >>b >>c >>d;
        arr[i]={{a,b},{c,d}};
        con.push_back(a),con.push_back(b),con.push_back(c);
    }
    con.push_back(1),con.push_back(m);
    sort(con.begin(),con.end());
    con.erase(unique(con.begin(),con.end()),con.end());
    //convert to 1 to con.size()
    m=con.size();
    for(int i=1;i<=n;i++){
        auto [pa,pb]=arr[i];
        auto [a,b]=pa;
        auto [c,d]=pb;
        arr[i]={{fd(a),fd(b)},{fd(c),d}};
    }
    stree sl,sr;
    sl.init(),sr.init();
    sl.update(1,m,1,1,0),sr.update(1,m,1,m,0);
    long long ans=LLONG_MAX;
    for(int i=1;i<=n;i++){
        auto [pa,pb]=arr[i];
        auto [a,b]=pa;
        auto [c,d]=pb;
        long long cl=sl.query(1,m,1,a,b),cr=sr.query(1,m,1,a,b);
        if(cl!=LLONG_MAX && cr!=LLONG_MAX){
            ans=min(ans,cl+cr+d);
        }
        if(cl!=LLONG_MAX) sl.update(1,m,1,c,cl+d);
        if(cr!=LLONG_MAX) sr.update(1,m,1,c,cr+d);
    }
    if(ans==LLONG_MAX) cout<<-1;
    else cout<<ans;
}

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