oj.uz

Submission #88084

# Submission time Handle Problem Language Result Execution time Memory
88084 2018-12-03T18:03:16 Z tincamatei Pinball (JOI14_pinball) C++14
51 / 100
 180 ms 10752 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_M = 100000;
const long long INF = 1000000000000000000LL;

int l[MAX_M], r[MAX_M], c[MAX_M], d[MAX_M];
int *pnt[3*MAX_M];
long long aint[1+4*MAX_M];
long long dpst[MAX_M], dpdr[MAX_M];

void init(int l = 1, int r = MAX_M, int nod = 1) {
    aint[nod] = INF;
    int mid = (l + r) / 2;
    if(l < r) {
        init(l, mid, 2 * nod);
        init(mid + 1, r, 2 * nod + 1);
    }
}

void update(int poz, long long val, int l = 1, int r = MAX_M, int nod = 1) {
    if(r < poz || poz < l) return;
    if(l == r)
        aint[nod] = min(aint[nod], val);
    else {
        int mid = (l + r) / 2;
        update(poz, val, l, mid, 2 * nod);
        update(poz, val, mid + 1, r, 2 * nod + 1);
        aint[nod] = min(aint[2 * nod], aint[2 * nod + 1]);
    }
}

long long query(int i, int j, int l = 1, int r = MAX_M, int nod = 1) {
    if(j < l || r < i) return INF;
    if(i <= l && r <= j) return aint[nod];

    if(l < r) {
        int mid = (l + r) / 2;
        return min(query(i, j, l, mid, 2 * nod),
                   query(i, j, mid + 1, r, 2 * nod + 1));
    }
    return INF;
}

bool cmp(int *a, int *b) {
    return *a < *b;
}

int normalize(int n) {
    for(int i = 0; i < n; ++i) {
        pnt[3*i] = &l[i];
        pnt[3*i + 1] = &r[i];
        pnt[3*i + 2] = &d[i];
    }

    std::sort(pnt, pnt + 3 * n, cmp);

    int last = *pnt[0], j = 1;
    for(int i = 0; i < 3 * n; ++i)
        if(*pnt[i] == last)
            *pnt[i] = j;
        else {
            ++j;
            last = *pnt[i];
            *pnt[i] = j;
        }
    return j;
}

int main() {
    int m, n, valmax;
    bool smallboi = 0, bigboi = 0;
    scanf("%d%d", &m, &n);
    for(int i = 0; i < m; ++i) {
        scanf("%d%d%d%d", &l[i], &r[i], &d[i], &c[i]);
        if(l[i] == 1)
            smallboi = true;
        if(r[i] == n)
            bigboi = true;
    }

    valmax = normalize(m);

    init();
    update(1, 0);
    for(int i = 0; i < m; ++i) {
        dpst[i] = query(l[i], r[i]);
        dpst[i] = min(INF, dpst[i] + c[i]);
        update(d[i], dpst[i]);
    }

    init();
    update(valmax, 0);
    for(int i = 0; i < m; ++i) {
        dpdr[i] = query(l[i], r[i]);
        dpdr[i] = min(INF, dpdr[i] + c[i]);
        update(d[i], dpdr[i]);
    }

    if(smallboi && bigboi) {
        long long rez = INF;
        for(int i = 0; i < m; ++i)
            if(dpst[i] != INF && dpdr[i] != INF)
                rez = min(dpst[i] + dpdr[i] - c[i], rez);

        if(rez == INF)
            printf("-1");
        else
            printf("%lld", rez);
    } else
        printf("-1");
    return 0;
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &m, &n);
     ~~~~~^~~~~~~~~~~~~~~~
pinball.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", &l[i], &r[i], &d[i], &c[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2424 KB Output is correct
2 Correct 5 ms 2556 KB Output is correct
3 Correct 5 ms 2556 KB Output is correct
4 Correct 5 ms 2672 KB Output is correct
5 Correct 5 ms 2800 KB Output is correct
6 Correct 5 ms 2800 KB Output is correct
7 Correct 5 ms 2800 KB Output is correct
8 Correct 5 ms 2800 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2424 KB Output is correct
2 Correct 5 ms 2556 KB Output is correct
3 Correct 5 ms 2556 KB Output is correct
4 Correct 5 ms 2672 KB Output is correct
5 Correct 5 ms 2800 KB Output is correct
6 Correct 5 ms 2800 KB Output is correct
7 Correct 5 ms 2800 KB Output is correct
8 Correct 5 ms 2800 KB Output is correct
9 Correct 5 ms 2800 KB Output is correct
10 Correct 5 ms 2800 KB Output is correct
11 Correct 5 ms 2800 KB Output is correct
12 Correct 6 ms 2800 KB Output is correct
13 Correct 6 ms 2800 KB Output is correct
14 Correct 6 ms 2820 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2424 KB Output is correct
2 Correct 5 ms 2556 KB Output is correct
3 Correct 5 ms 2556 KB Output is correct
4 Correct 5 ms 2672 KB Output is correct
5 Correct 5 ms 2800 KB Output is correct
6 Correct 5 ms 2800 KB Output is correct
7 Correct 5 ms 2800 KB Output is correct
8 Correct 5 ms 2800 KB Output is correct
9 Correct 5 ms 2800 KB Output is correct
10 Correct 5 ms 2800 KB Output is correct
11 Correct 5 ms 2800 KB Output is correct
12 Correct 6 ms 2800 KB Output is correct
13 Correct 6 ms 2800 KB Output is correct
14 Correct 6 ms 2820 KB Output is correct
15 Correct 5 ms 2844 KB Output is correct
16 Correct 6 ms 2848 KB Output is correct
17 Correct 7 ms 2988 KB Output is correct
18 Correct 7 ms 3028 KB Output is correct
19 Correct 7 ms 3068 KB Output is correct
20 Correct 7 ms 3108 KB Output is correct
21 Correct 6 ms 3108 KB Output is correct
22 Correct 7 ms 3164 KB Output is correct
23 Correct 7 ms 3200 KB Output is correct
24 Correct 7 ms 3244 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2424 KB Output is correct
2 Correct 5 ms 2556 KB Output is correct
3 Correct 5 ms 2556 KB Output is correct
4 Correct 5 ms 2672 KB Output is correct
5 Correct 5 ms 2800 KB Output is correct
6 Correct 5 ms 2800 KB Output is correct
7 Correct 5 ms 2800 KB Output is correct
8 Correct 5 ms 2800 KB Output is correct
9 Correct 5 ms 2800 KB Output is correct
10 Correct 5 ms 2800 KB Output is correct
11 Correct 5 ms 2800 KB Output is correct
12 Correct 6 ms 2800 KB Output is correct
13 Correct 6 ms 2800 KB Output is correct
14 Correct 6 ms 2820 KB Output is correct
15 Correct 5 ms 2844 KB Output is correct
16 Correct 6 ms 2848 KB Output is correct
17 Correct 7 ms 2988 KB Output is correct
18 Correct 7 ms 3028 KB Output is correct
19 Correct 7 ms 3068 KB Output is correct
20 Correct 7 ms 3108 KB Output is correct
21 Correct 6 ms 3108 KB Output is correct
22 Correct 7 ms 3164 KB Output is correct
23 Correct 7 ms 3200 KB Output is correct
24 Correct 7 ms 3244 KB Output is correct
25 Correct 28 ms 3940 KB Output is correct
26 Correct 66 ms 5644 KB Output is correct
27 Incorrect 180 ms 10752 KB Output isn't correct
28 Halted 0 ms 0 KB -