Submission #564273

#	Time	Username	Problem	Language	Result	Execution time	Memory
564273		urosk	Pinball (JOI14_pinball)	C++14	0 / 100	4 ms	6612 KiB

pinball

// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;

#define maxn 200005
ll n,m;
ll l[maxn],r[maxn],c[maxn],val[maxn];
ll t[4*maxn];
void upd(ll v,ll tl,ll tr,ll i,ll x){
    if(tl==tr){
        t[v] = x;
        return;
    }
    ll mid = (tl+tr)/2;
    if(i<=mid) upd(2*v,tl,mid,i,x);
    else upd(2*v+1,mid+1,tr,i,x);
    t[v] = min(t[2*v],t[2*v+1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r){
    if(l>r) return llinf;
    if(tl==l&&tr==r) return t[v];
    ll mid = (tl+tr)/2;
    return min(get(2*v,tl,mid,l,min(mid,r)),get(2*v+1,mid+1,tr,max(mid+1,l),r));
}
ll it = 1;
map<ll,ll> mp;
ll dp[maxn][2];
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> m;
    set<ll> s;
    s.insert(1);
    s.insert(m);
    for(ll i = 1;i<=n;i++){
        cin >> l[i] >> r[i] >> c[i] >> val[i];
        s.insert(l[i]);
        s.insert(r[i]);
        s.insert(c[i]);
    }
    for(ll x : s) mp[x] = it++;
    m = mp[m];
    for(ll i = 1;i<=n;i++){
        l[i] = mp[l[i]];
        r[i] = mp[r[i]];
        c[i] = mp[c[i]];
    }
    vector<ll> w = {1,m};
    for(ll ii = 0;ii<2;ii++){
        fill(t,t+4*maxn,llinf);
        upd(1,1,it+1,w[ii],0);
        for(ll i = 1;i<=n;i++){
            dp[i][ii] = get(1,1,it+1,l[i],r[i]);
            upd(1,1,it+1,c[i],dp[i][ii] + val[i]);
        }
    }
    ll ans = llinf;
    for(ll i = 1;i<=n;i++) ans = min(ans,dp[i][0] + dp[i][1] + val[i]);
	if(ans==llinf) ans = -1;
	cout<<ans<<endl;
	return 0;
}
/*
5 6
2 4 3 5
1 2 2 8
3 6 5 2
4 6 4 7
2 4 3 10
*/

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