Submission #995618

#	Time	Username	Problem	Language	Result	Execution time	Memory
995618		amine_aroua	Pinball (JOI14_pinball)	C++17	100 / 100	339 ms	43192 KiB

pinball

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define intt long long
#define pb push_back
#define nl '\n'
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i, x, y) for(int i = x;i<=y;i++)
#define forn(i, y, x) for(int i = y; i >= x; i--)
const int M = (1<<19);
intt n , m , o;
vector<tuple<intt , intt , intt,intt>> intervals;
const intt INF = 1e18;
struct segTree
{
    vector<intt> tree;
    void init()
    {
        tree.assign(2*M , INF);
    }
    void upd(intt i , intt x)
    {
        tree[i + M] = min(tree[i + M] , x);
        for(intt j = (i + M) / 2 ; j>=1;j/=2)
        {
            tree[j] = min(tree[2*j] , tree[2*j + 1]);
        }
    }
    intt query(intt l , intt r)
    {
        l+=M;
        r+=M;
        if(l == r)
            return tree[l];
        intt lt = tree[l] , rt = tree[r];
        while(l + 1 < r)
        {
            if(l % 2 == 0)
                lt = min(lt , tree[l + 1]);
            if(r%2 == 1)
                rt = min(tree[r - 1] , rt);
            l>>=1;
            r>>=1;
        }
        return min(lt , rt);
    }
}dp[2];

void rakkah()
{
    map<intt ,intt> compress;
    o = 1;
    compress[n] = 1;
    compress[o] = 1;
    forr(i , 1 , m)
    {
        intt a , b , c , d;
        cin>>a>>b>>c>>d;
        compress[a] = compress[b] = compress[c] = 1;
        intervals.pb({a , b , c , d});
    }
    intt cnt = 0;
    for(auto p : compress)
    {
        compress[p.first] = cnt++;
    }
    n = compress[n] ;
    o = compress[o];
    for(auto &[a , b , c , d] : intervals)
    {
        a = compress[a] , b = compress[b] , c = compress[c];
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    fore(i , 2)dp[i].init();
    cin>>m>>n;
    rakkah();
    intt ans = INF;
    fore(i , m)
    {
        auto [a , b , c ,d] = intervals[i];
        intt cur[2] = {INF , INF};
        if(a == o)
            cur[0] = d;
        if(b == n)
            cur[1] = d;
        fore(j , 2)
        {
            cur[j] = min(cur[j] , d + dp[j].query(a , b));
        }
        fore(j , 2)
            dp[j].upd(c , cur[j]);
        ans = min(ans , cur[0] + cur[1] - d);
    }
    cout<<(ans >= 1e17 ? -1 : ans)<<nl;
}

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