oj.uz

Submission #314287

# Submission time Handle Problem Language Result Execution time Memory
314287 2020-10-19T12:41:10 Z mihai145 Pinball (JOI14_pinball) C++14
0 / 100
 1 ms 384 KB 
#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[4 * 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[4 * 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;
    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, a[i].A, 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, a[i].A, a[i].B));
        }

        st.Update(1, 1, k, a[i].C, minCostSt);
        dr.Update(1, 1, k, 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
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -