Submission #88084

#	Time	Username	Problem	Language	Result	Execution time	Memory
88084		tincamatei	Pinball (JOI14_pinball)	C++14	51 / 100	180 ms	10752 KiB

pinball

#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 (stderr)

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 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 49