Submission #1157020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1157020		dosts	Pinball (JOI14_pinball)	C++20	100 / 100	217 ms	29360 KiB

pinball

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define sp << " " <<    
#define all(cont) cont.begin(),cont.end()
#define vi vector<int>

const int inf = 1e17,N = 5e5+1,MOD =  998244353;


struct Segment {
    int a,b,c,p;
};


vi v;

int idx(int x) {
    return (upper_bound(all(v),x)-v.begin());
}

struct ST {
    vi t;

    ST(int nn) {
        t.assign(4*nn+1,inf);
    }

    void update(int node,int l,int r,int p,int v) {
        if (l == r) {
            t[node] = min(t[node],v);
            return;
        }
        int m = (l+r) >> 1;
        if (p <= m) update(2*node,l,m,p,v);
        else update(2*node+1,m+1,r,p,v);
        t[node] = min(t[2*node],t[2*node+1]);
    }

    int query(int node,int l,int r,int L,int R) {
        if (l > R || r < L ) return inf;
        if (l >= L && r <= R) return t[node];
        int m = (l+r) >> 1;
        return min(query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R)); 
    }

};

void solve() {  
    int m,n;
    cin >> m >> n;
    vector<Segment> segs(m+1);
    for (int i=1;i<=m;i++) {
        cin >> segs[i].a >> segs[i].b >> segs[i].c >> segs[i].p;
        v.push_back(segs[i].a);
        v.push_back(segs[i].b);
        v.push_back(segs[i].c);
    }
    v.push_back(1);
    v.push_back(n);
    sort(all(v));
    v.erase(unique(all(v)),v.end());
    int ans = inf;
    int sz = v.size();
    ST st(sz),st2(sz);
    vi dp(sz+1,inf),dp2(sz+1,inf);
    st.update(1,1,sz,1,0);
    st2.update(1,1,sz,sz,0);
    dp[1] = 0;
    dp2[sz] = 0; 
    //point update range max
    for (int i=1;i<=m;i++) {
        segs[i].a = idx(segs[i].a);
        segs[i].b = idx(segs[i].b);
        segs[i].c = idx(segs[i].c);
        ans = min(ans,st.query(1,1,sz,segs[i].a,segs[i].b)+st2.query(1,1,sz,segs[i].a,segs[i].b)+segs[i].p);
        dp[segs[i].c] = min(dp[segs[i].c],st.query(1,1,sz,segs[i].a,sz)+segs[i].p);
        st.update(1,1,sz,segs[i].c,dp[segs[i].c]);
        dp2[segs[i].c] = min(dp2[segs[i].c],st2.query(1,1,sz,1,segs[i].b)+segs[i].p);
        st2.update(1,1,sz,segs[i].c,dp2[segs[i].c]);
    }
    if (ans >= inf) cout << -1 << '\n';
    else cout << ans << '\n';
}


int32_t main() { 
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifdef Dodi 
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

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