Submission #314289

#	Time	Username	Problem	Language	Result	Execution time	Memory
314289		mihai145	Pinball (JOI14_pinball)	C++14	100 / 100	735 ms	45952 KiB

pinball

#include <iostream>
#include <set>
#include <unordered_map>

using namespace std;

const long long INF = 1e18;
const int MMAX = 1e5;

int M, N;

struct device
{
    int A, B, C, D;
};
device a[MMAX + 2];

int k;
unordered_map <int, int> norm;

long long minAns = INF;

struct AintSt
{

    long long v[12 * MMAX];

    void Build(int node, int st, int dr)
    {

        v[node] = INF;

        if(st == dr)
        {
            return;
        }

        int mid = (st + dr) >> 1;
        Build(2 * node, st, mid);
        Build(2 * node + 1, mid + 1, dr);
    }

    void Update(int node, int st, int dr, int pos, long long val)
    {
        if(st == dr)
        {
            v[node] = min(v[node], val);
            return ;
        }

        int mid = (st + dr) >> 1;
        if(pos <= mid)
            Update(2 * node, st, mid, pos, val);
        else
            Update(2 * node + 1, mid + 1, dr, pos, val);

        v[node] = min(v[2 * node], v[2 * node + 1]);
    }

    long long Query(int node, int st, int dr, int l, int r)
    {
        if(l <= st && dr <= r)
            return v[node];

        if(dr < l || r < st)
            return INF;

        int mid = (st + dr) >> 1;
        long long a1 = Query(2 * node, st, mid, l, r);
        long long a2 = Query(2 * node + 1, mid + 1, dr, l, r);

        return min(a1, a2);
    }
};

struct AintDr
{
    long long v[12 * MMAX];

    void Build(int node, int st, int dr)
    {

        v[node] = INF;

        if(st == dr)
        {
            return;
        }

        int mid = (st + dr) >> 1;
        Build(2 * node, st, mid);
        Build(2 * node + 1, mid + 1, dr);
    }

    void Update(int node, int st, int dr, int pos, long long val)
    {
        if(st == dr)
        {
            v[node] = min(v[node], val);
            return ;
        }

        int mid = (st + dr) >> 1;
        if(pos <= mid)
            Update(2 * node, st, mid, pos, val);
        else
            Update(2 * node + 1, mid + 1, dr, pos, val);

        v[node] = min(v[2 * node], v[2 * node + 1]);
    }

    long long Query(int node, int st, int dr, int l, int r)
    {
        if(l <= st && dr <= r)
            return v[node];

        if(dr < l || r < st)
            return INF;

        int mid = (st + dr) >> 1;
        long long a1 = Query(2 * node, st, mid, l, r);
        long long a2 = Query(2 * node + 1, mid + 1, dr, l, r);

        return min(a1, a2);
    }
};

AintSt st;
AintDr dr;

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

    cin >> M >> N;

    set <int> coord; ///pot avea maxim 3 * M + 2 coordonate distincte
    coord.insert(1), coord.insert(N);

    for(int i = 1; i <= M; i++)
    {
        cin >> a[i].A >> a[i].B >> a[i].C >> a[i].D;
        coord.insert(a[i].A);
        coord.insert(a[i].B);
        coord.insert(a[i].C);
    }

    for(auto it : coord)
        norm[it] = ++k;

    st.Build(1, 1, k);
    dr.Build(1, 1, k);

    for(int i = 1; i <= M; i++)
    {

        long long minCostSt = INF, minCostDr = INF;

        if(norm[a[i].A] == 1)
        {
            minCostSt = a[i].D;
        }
        else
        {
            minCostSt = min(minCostSt, a[i].D + st.Query(1, 1, k, norm[a[i].A], norm[a[i].B]));
        }

        if(norm[a[i].B] == k)
        {
            minCostDr = a[i].D;
        }
        else
        {
            minCostDr = min(minCostDr, a[i].D + dr.Query(1, 1, k, norm[a[i].A], norm[a[i].B]));
        }

        st.Update(1, 1, k, norm[a[i].C], minCostSt);
        dr.Update(1, 1, k, norm[a[i].C], minCostDr);

        long long minCostCurr = min(INF, minCostSt + minCostDr - a[i].D);
        minAns = min(minAns, minCostCurr);
    }

    if(minAns >= INF)
        cout << -1 << '\n';
    else
        cout << minAns << '\n';

    return 0;
}

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