oj.uz

Submission #314288

# Submission time Handle Problem Language Result Execution time Memory
314288 2020-10-19T12:42:48 Z mihai145 Pinball (JOI14_pinball) C++14
51 / 100
 322 ms 47168 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, 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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 768 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 3 ms 768 KB Output is correct
23 Correct 3 ms 768 KB Output is correct
24 Correct 3 ms 768 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 512 KB Output is correct
17 Correct 2 ms 512 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 3 ms 768 KB Output is correct
20 Correct 3 ms 512 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 3 ms 768 KB Output is correct
23 Correct 3 ms 768 KB Output is correct
24 Correct 3 ms 768 KB Output is correct
25 Correct 27 ms 3200 KB Output is correct
26 Correct 95 ms 7684 KB Output is correct
27 Correct 322 ms 14620 KB Output is correct
28 Correct 166 ms 2156 KB Output is correct
29 Correct 231 ms 13340 KB Output is correct
30 Correct 222 ms 4600 KB Output is correct
31 Runtime error 281 ms 47168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Halted 0 ms 0 KB -