답안 #88088 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88088	2018-12-03T18:55:45 Z	tincamatei	Pinball (JOI14_pinball)	C++14	100 / 100	319 ms	49888 KB

pinball

#include <bits/stdc++.h>

using namespace std;

const int MAX_M = 100000;
const long long INF = 1LL << 60;

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

void init(int l = 1, int r = 3*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 = 3*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 = 3*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

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	8568 KB	Output is correct
2	Correct	12 ms	8692 KB	Output is correct
3	Correct	12 ms	8768 KB	Output is correct
4	Correct	11 ms	8768 KB	Output is correct
5	Correct	11 ms	8768 KB	Output is correct
6	Correct	11 ms	8876 KB	Output is correct
7	Correct	12 ms	8876 KB	Output is correct
8	Correct	12 ms	8876 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	8568 KB	Output is correct
2	Correct	12 ms	8692 KB	Output is correct
3	Correct	12 ms	8768 KB	Output is correct
4	Correct	11 ms	8768 KB	Output is correct
5	Correct	11 ms	8768 KB	Output is correct
6	Correct	11 ms	8876 KB	Output is correct
7	Correct	12 ms	8876 KB	Output is correct
8	Correct	12 ms	8876 KB	Output is correct
9	Correct	12 ms	8880 KB	Output is correct
10	Correct	11 ms	8880 KB	Output is correct
11	Correct	12 ms	8880 KB	Output is correct
12	Correct	12 ms	8880 KB	Output is correct
13	Correct	14 ms	8880 KB	Output is correct
14	Correct	13 ms	8880 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	8568 KB	Output is correct
2	Correct	12 ms	8692 KB	Output is correct
3	Correct	12 ms	8768 KB	Output is correct
4	Correct	11 ms	8768 KB	Output is correct
5	Correct	11 ms	8768 KB	Output is correct
6	Correct	11 ms	8876 KB	Output is correct
7	Correct	12 ms	8876 KB	Output is correct
8	Correct	12 ms	8876 KB	Output is correct
9	Correct	12 ms	8880 KB	Output is correct
10	Correct	11 ms	8880 KB	Output is correct
11	Correct	12 ms	8880 KB	Output is correct
12	Correct	12 ms	8880 KB	Output is correct
13	Correct	14 ms	8880 KB	Output is correct
14	Correct	13 ms	8880 KB	Output is correct
15	Correct	12 ms	8880 KB	Output is correct
16	Correct	12 ms	8880 KB	Output is correct
17	Correct	13 ms	8880 KB	Output is correct
18	Correct	13 ms	8952 KB	Output is correct
19	Correct	14 ms	8952 KB	Output is correct
20	Correct	15 ms	8956 KB	Output is correct
21	Correct	13 ms	8956 KB	Output is correct
22	Correct	14 ms	8956 KB	Output is correct
23	Correct	13 ms	8956 KB	Output is correct
24	Correct	14 ms	8956 KB	Output is correct

Subtask #4
49.0 / 49.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	8568 KB	Output is correct
2	Correct	12 ms	8692 KB	Output is correct
3	Correct	12 ms	8768 KB	Output is correct
4	Correct	11 ms	8768 KB	Output is correct
5	Correct	11 ms	8768 KB	Output is correct
6	Correct	11 ms	8876 KB	Output is correct
7	Correct	12 ms	8876 KB	Output is correct
8	Correct	12 ms	8876 KB	Output is correct
9	Correct	12 ms	8880 KB	Output is correct
10	Correct	11 ms	8880 KB	Output is correct
11	Correct	12 ms	8880 KB	Output is correct
12	Correct	12 ms	8880 KB	Output is correct
13	Correct	14 ms	8880 KB	Output is correct
14	Correct	13 ms	8880 KB	Output is correct
15	Correct	12 ms	8880 KB	Output is correct
16	Correct	12 ms	8880 KB	Output is correct
17	Correct	13 ms	8880 KB	Output is correct
18	Correct	13 ms	8952 KB	Output is correct
19	Correct	14 ms	8952 KB	Output is correct
20	Correct	15 ms	8956 KB	Output is correct
21	Correct	13 ms	8956 KB	Output is correct
22	Correct	14 ms	8956 KB	Output is correct
23	Correct	13 ms	8956 KB	Output is correct
24	Correct	14 ms	8956 KB	Output is correct
25	Correct	34 ms	9344 KB	Output is correct
26	Correct	71 ms	10236 KB	Output is correct
27	Correct	204 ms	12648 KB	Output is correct
28	Correct	225 ms	18064 KB	Output is correct
29	Correct	141 ms	18064 KB	Output is correct
30	Correct	253 ms	24052 KB	Output is correct
31	Correct	297 ms	27812 KB	Output is correct
32	Correct	273 ms	31708 KB	Output is correct
33	Correct	54 ms	31708 KB	Output is correct
34	Correct	135 ms	31708 KB	Output is correct
35	Correct	212 ms	38192 KB	Output is correct
36	Correct	319 ms	42148 KB	Output is correct
37	Correct	308 ms	46012 KB	Output is correct
38	Correct	283 ms	49888 KB	Output is correct

답안 #88088

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 18.0 / 18.0

Subtask #3 22.0 / 22.0

Subtask #4 49.0 / 49.0

Subtask #1
11.0 / 11.0

Subtask #2
18.0 / 18.0

Subtask #3
22.0 / 22.0

Subtask #4
49.0 / 49.0