Submission #1247159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247159		nguyenhuythach	Pinball (JOI14_pinball)	C++20	100 / 100	382 ms	55928 KiB

pinball

#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
#define MASK(i) ((1)<<(i))
#define rngdcl mt19937_64 rng(chrono::steady_clock::now().time_asince_epoch().count())
#define random(l,r) ((l)+(rng()%(r-l+1)))
using namespace std;
const int nmax=5e5+1;
int m,n,crr=0;
int a[nmax],b[nmax],c[nmax],d[nmax],ans[nmax];
map<int,int> mp;
set<int> s;

void input()
{
    cin >> m >> n;
    FOR(i,1,m) cin >> a[i] >> b[i] >> c[i] >> d[i];
}

struct SEGTREE
{
    vector<int> tree;
    int n;
    
    SEGTREE (int N)
    {
        n=N;
        tree.resize(4*n+5,L);
    }
    
    void update(int id,int l,int r,int x,int val)
    {
        if(x<l || r<x) return;
        if(l==r)
        {
            tree[id]=min(tree[id],val);
            return;
        }
        int mid=(l+r)/2;
        update(id*2,l,mid,x,val);
        update(id*2+1,mid+1,r,x,val);
        tree[id]=min(tree[id*2],tree[id*2+1]);
    }
    
    int get(int id,int l,int r,int x,int y)
    {
        if(y<l || r<x) return L;
        if(x<=l && r<=y) return tree[id];
        int mid=(l+r)/2;
        return min(get(id*2,l,mid,x,y),get(id*2+1,mid+1,r,x,y));
    }
    
    void update(int x,int val)
    {
        update(1,1,n,x,val);
    }
    
    int get(int l,int r)
    {
        return get(1,1,n,l,r);
    }
};

void compress()
{
    s.insert(1);
    s.insert(n);
    FOR(i,1,m)
    {
        s.insert(a[i]);
        s.insert(b[i]);
        s.insert(c[i]);
    }
    FORD(i,s) mp[i]=++crr;
    FOR(i,1,m)
    {
        a[i]=mp[a[i]];
        b[i]=mp[b[i]];
        c[i]=mp[c[i]];
    }
}

void solve()
{
    compress();
    SEGTREE st1(crr);
    SEGTREE st2(crr);
    st1.update(mp[1],0);
    st2.update(mp[n],0);
    FOR(i,1,m) ans[i]=L;
    FOR(i,1,m)
    {
        int lf=st1.get(a[i],b[i]);
        int rt=st2.get(a[i],b[i]);
        if(lf!=L) st1.update(c[i],lf+d[i]);
        if(rt!=L) st2.update(c[i],rt+d[i]);
        if(lf!=L && rt!=L) ans[i]=lf+rt+d[i];
    }
    int res=L;
    FOR(i,1,m) res=min(res,ans[i]);
    if(res==L) cout << -1;
    else cout << res;
}

signed main()
{
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    input();
    solve();
}

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