Submission #349305

#	Time	Username	Problem	Language	Result	Execution time	Memory
349305		iliccmarko	Pinball (JOI14_pinball)	C++14	100 / 100	997 ms	61576 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 10000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define single_case solve();
#define line cerr<<"----------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); }
#define mod 1000000007LL
const int N = 1e6 + 5;
ll a[N], b[N], c[N], d[N];
ll n, m;
ll seg[4*N];
ll l[N], r[N];
ll rev[N];

inline ll get_min(ll node, ll l, ll r, ll i, ll j)
{
    if(i>r||j<l) return LINF;
    if(i>=l&&j<=r) return seg[node];
    ll mid = (i+j)/2;
    return min(get_min(node*2+1, l, r, i, mid), get_min(node*2+2, l, r, mid+1, j));
}

inline void update(ll node, ll l, ll r, ll pos, ll x)
{
    if(l==r)
    {
        seg[node] = min(seg[node], x);
        return;
    }
    ll mid = (l+r)/2;
    if(pos>mid) update(node*2+2, mid+1, r, pos, x);
    else update(node*2+1, l, mid, pos, x);
    seg[node] = min(seg[node*2+1], seg[node*2+2]);
}
map<ll, ll> mm;
vector<ll> s;

int main()
{
    ios
    cin>>m>>n;
    for(int i = 0;i<m;i++)
    {
        cin>>a[i]>>b[i]>>c[i]>>d[i];
        s.pb(a[i]);
        s.pb(b[i]);
        s.pb(c[i]);
    }
    sort(all(s));
    ll val = 0;
    for(int i = 0;i<len(s);i++)
    {
        if(!i||s[i]!=s[i-1]) mm[s[i]] = ++val;
    }
    for(int i = 0;i<4*N;i++) seg[i] = LINF;
    for(int i = 0;i<m;i++)
    {
        if(a[i]==1)
        {
            l[i] = d[i];
            update(0, 1, val, mm[c[i]], l[i]);
            continue;
        }
        //cout<<mm[a[i]]<<" "<<mm[b[i]]<<endl;
        ll mini = get_min(0, mm[a[i]], mm[b[i]], 1, val);
        l[i] = min(LINF, mini+d[i]);
        update(0, 1, val, mm[c[i]], l[i]);
    }
    for(int i = 0;i<4*N;i++) seg[i] = LINF;
    for(int i = 0;i<m;i++)
    {
        if(b[i]==n)
        {
            r[i] = d[i];
            update(0, 1, val, mm[c[i]], r[i]);
            continue;
        }
        ll mini = get_min(0, mm[a[i]], mm[b[i]], 1, val);
        r[i] = min(LINF, mini+d[i]);
        update(0, 1, val, mm[c[i]], r[i]);
    }
    ll ans = LINF;
    for(int i = 0;i<m;i++) ans = min(ans, l[i]+r[i]-d[i]);
    //for(int i = 0;i<m;i++) cout<<l[i]<<" "<<r[i]<<endl;
    if(ans==LINF) cout<<-1;
    else cout<<ans;








    return 0;
}

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