제출 #1160674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160674		SSSM	Pinball (JOI14_pinball)	C++20	100 / 100	195 ms	68540 KiB

pinball

#include <bits/stdc++.h>

/*
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx2")
*/


using namespace std;

/*
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
*/

#define F first
#define S second
#define pb push_back
#define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define md(a) ((a%mod+mod)%mod)
#define all(a) a.begin(), a.end()
#define MP make_pair
#define lc (id<<1)
#define rc (lc|1)
#define mid (l+r)/2
#define SZ(a) (ll)(a.size())
#define kill(a) cout << a << "\n", exit(0)
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
mt19937_64  rng(chrono::steady_clock::now().time_since_epoch().count());

ll const maxn=1e6+10, mod=1e9+7, INF=1e18, LOG=31, sq=200;

ll poww(ll a, ll b, ll mod) {
 if (b == 0) return 1;
 return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod;
}

ll m, n, A[maxn], B[maxn], C[maxn], D[maxn];
vector<ll> comp;
struct SegTree{
    ll seg[maxn<<2];
    void init(){
        fill(seg, seg+maxn*4, INF);
    }
    void Set(ll p, ll x, ll l=0, ll r=SZ(comp), ll id=1)
    {
        if(l==r-1)
        {
            seg[id]=min(seg[id], x);
            return;
        }
        if(p<mid) Set(p, x, l, mid, lc);
        else Set(p, x, mid, r, rc);
        seg[id]=min(seg[lc], seg[rc]);
    }
    ll Get(ll s, ll e, ll l=0, ll r=SZ(comp), ll id=1)
    {
        if(l>=e || r<=s) return INF;
        if(s<=l && r<=e) return seg[id];
        return min(Get(s, e, l, mid, lc), Get(s, e, mid, r, rc));
    }
} dp1, dp2;

int main(){
    
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin>>m>>n;
    for(ll i=1;i<=m;i++)
    {
        cin>>A[i]>>B[i]>>C[i]>>D[i];
        comp.pb(A[i]);comp.pb(B[i]);comp.pb(C[i]);
    }
    comp.pb(1);
    comp.pb(n);
    sort(all(comp));
    comp.resize(unique(all(comp))-comp.begin());
    n=SZ(comp);
    for(ll i=1;i<=m;i++)
    {
        A[i]=lower_bound(all(comp), A[i])-comp.begin();
        B[i]=lower_bound(all(comp), B[i])-comp.begin();
        C[i]=lower_bound(all(comp), C[i])-comp.begin();
    }
    dp1.init();dp2.init();
    dp1.Set(0, 0);
    dp2.Set(n-1, 0);
    ll ans=INF;
    for(ll i=1;i<=m;i++)
    {
        ll x=dp1.Get(A[i], B[i]+1);
        ll y=dp2.Get(A[i], B[i]+1);
        //cout<<i<<" "<<A[i]<<" "<<B[i]<<" "<<x<<" "<<y<<"+++++\n";
        ans=min(ans, x+y+D[i]);
        if(x+D[i]<dp1.Get(C[i], C[i]+1)) dp1.Set(C[i], x+D[i]);
        if(y+D[i]<dp2.Get(C[i], C[i]+1)) dp2.Set(C[i], y+D[i]);
    }
    if(ans>=INF) ans=-1;
    cout<<ans<<"\n";



    return 0;
}

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