Submission #1095295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095295		Saul0906	Pinball (JOI14_pinball)	C++14	100 / 100	543 ms	94288 KiB

pinball

#include <bits/stdc++.h>
#define ll long long
 
using namespace std;
 
ll inf=1e18;
 
struct device{
    ll i, a, b, c, d;
    ll dp[2]={inf, inf};
    bool operator<(const device B)const{
        return b<B.b;
    }
};
 
struct segtree{
    segtree *left, *right;
    int l, r, mid;
    ll mn=inf;
    segtree(int x, int y){
        l=x;
        r=y;
        mid=(l+r)/2;
        if(l==r) return;
        left = new segtree(l,mid);
        right = new segtree(mid+1,r);
    }
    void update(int x, ll dp, bool force=false){
        if(x<l || r<x) return;
        if(x<=l && r<=x){
            mn=min(dp,mn);
            if(force) mn=dp;
            return;
        }
        left->update(x,dp,force);
        right->update(x,dp,force);
        mn=min(left->mn,right->mn);
    }
    ll query(int x, int y){
        if(y<l || r<x) return 1e18;
        if(x<=l && r<=y) return mn;
        return min(left->query(x,y),right->query(x,y));
    }
};
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin>>n>>m;
    vector<device> devs(n);
    ll ans=1e18;
    map<int, int> ccmp;
    set<int> nums;
    for(int i=0; i<n; i++){
        cin>>devs[i].a>>devs[i].b>>devs[i].c>>devs[i].d;
        devs[i].i=i;
        nums.insert(devs[i].a);
        nums.insert(devs[i].b);
        nums.insert(devs[i].c);
    }
    nums.insert(1);
    nums.insert(m);
    int x=0;
    for(auto e:nums) ccmp[e]=x++;
    segtree ST(0,x), ST2(0,x);
    ST.update(0,0);
    for(int i=0; i<n; i++){
        devs[i].a=ccmp[devs[i].a];
        devs[i].b=ccmp[devs[i].b];
        devs[i].c=ccmp[devs[i].c];
    }
    for(int i=0; i<n; i++){
        devs[i].dp[0]=ST.query(devs[i].a,devs[i].b)+devs[i].d;
        ST.update(devs[i].c,devs[i].dp[0]);
    }
    ST2.update(x-1,0);
    for(int i=0; i<n; i++){
        devs[i].dp[1]=ST2.query(devs[i].a,devs[i].b)+devs[i].d;
        ST2.update(devs[i].c,devs[i].dp[1]);
        ans=min(ans,devs[i].dp[1]+devs[i].dp[0]-devs[i].d);
        //cout<<devs[i].a<<" "<<devs[i].b<<" "<<devs[i].c<<" "<<devs[i].dp[0]<<" "<<devs[i].dp[1]<<endl;
    }
    if(ans==inf) cout<<-1<<endl;
    else cout<<ans<<endl;
}

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