Submission #292557

#	Time	Username	Problem	Language	Result	Execution time	Memory
292557		davooddkareshki	Pinball (JOI14_pinball)	C++17	100 / 100	807 ms	47332 KiB

pinball

// be name khoda
#include<bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define int long long
#define mpr make_pair 
typedef long long ll;
#pragma GCC optimize("Ofast")

const int maxn = 3e5+10;
const int mod = 1e9+7;
const ll inf = 1e18+10;

int n, m, k;
struct segment
{
    ll seg[maxn<<2];

    segment()
    {
        fill(seg, seg+maxn*4, inf);
    }

    void modify(int pos, int val, int v = 1, int tl = 1, int tr = n)
    {
        seg[v] = min(seg[v], val);
        if(tl == tr) return;
        
        int tm = (tl + tr) >> 1;
        if(pos <= tm) modify(pos, val, v<<1, tl, tm);
        else modify(pos, val, v<<1|1, tm+1, tr);
    }

    int qu(int l, int r, int v = 1, int tl = 1, int tr = n)
    {
        if(l > r) return inf;
        if(tl == l && tr == r) return seg[v];

        int tm = (tl + tr) >> 1;
        return min(qu(l, min(tm,r), v<<1, tl, tm),
                    qu(max(tm+1,l), r, v<<1|1, tm+1, tr));
    }   
} seg1, seg2;

int a[maxn], b[maxn], c[maxn], d[maxn];

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin>> m >> n;
    if(n == 1) return cout<< 0, 0;

    map<int,int> mp;
    vector<int> ve;
    for(int i = 1; i <= m; i++)
    {
        cin>> a[i] >> b[i] >> c[i] >> d[i];
        ve.push_back(a[i]);
        ve.push_back(b[i]);
        ve.push_back(c[i]);
    }
    sort(ve.begin(), ve.end());
    if(ve.back() < n) return cout<< -1, 0;
    if(ve[0] > 1) return cout<< -1, 0;

    int lst = 0; for(auto x : ve) if(!mp.count(x)) mp.insert({x,++lst});
    n = lst;

    seg1.modify(1,0); seg2.modify(n,0);
    ll ans = inf;
    for(int i = 1; i <= m; i++)
    {
        a[i] = mp[a[i]];
        b[i] = mp[b[i]];
        c[i] = mp[c[i]];

        int val1 = seg1.qu(a[i],b[i]);
        seg1.modify(c[i], val1+d[i]);
        
        int val2 = seg2.qu(a[i],b[i]);
        seg2.modify(c[i], val2+d[i]);

        ans = min(ans, seg1.qu(a[i],b[i]) + seg2.qu(a[i],b[i]) + d[i]);
    }

    if(ans < inf) cout<< ans;
    else cout<< -1;
}

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