oj.uz

Submission #40357

# Submission time Handle Problem Language Result Execution time Memory
40357 2018-01-31T11:34:11 Z krauch Pinball (JOI14_pinball) C++14
100 / 100
 437 ms 78916 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > PII;

#define F first
#define S second
#define mkp make_pair
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define left(a) a << 1
#define right(a) a << 1 | 1

const ll ool = 1e18 + 9;
const int N = 3e5 + 3, oo = 1e9 + 9;

int n, m, a[N], b[N], c[N], cost[N];
ll d[N], ans = ool;
vector < PII > vec;

struct SegTree {
    ll mn[N * 4], add[N * 4];

    void recalc(int v) {
        mn[v] = min(mn[left(v)], mn[right(v)]);
    }

    void build(int v, int tl, int tr) {
        add[v] = ool;
        if (tl == tr - 1) {
            mn[v] = ool;
            return;
        }
        int mid = (tl + tr) >> 1;
        build(left(v), tl, mid);
        build(right(v), mid, tr);
        recalc(v);
    }

    void push(int v, int tl, int tr) {
        if (tl < tr - 1) {
            add[left(v)] = min(add[left(v)], add[v]);
            add[right(v)] = min(add[right(v)], add[v]);
        }
        mn[v] = min(mn[v], add[v]);
        add[v] = ool;
    }

    void upd(int v, int tl, int tr, int ql, int qr, ll val) {
        push(v, tl, tr);
        if (tr <= ql || qr <= tl) return;
        if (ql <= tl && tr <= qr) {
            add[v] = min(add[v], val);
            push(v, tl, tr);
            return;
        }
        int mid = (tl + tr) >> 1;
        upd(left(v), tl, mid, ql, qr, val);
        upd(right(v), mid, tr, ql, qr, val);
        recalc(v);
    }

    ll get(int v, int tl, int tr, int ql, int qr) {
        push(v, tl, tr);
        if (tr <= ql || qr <= tl) return ool;
        if (ql <= tl && tr <= qr) return mn[v];
        int mid = (tl + tr) >> 1;
        return min(get(left(v), tl, mid, ql, qr), get(right(v), mid, tr, ql, qr));
    }
} t[2];

int main() {
    #ifdef krauch
        freopen("input.txt", "r", stdin);
    #endif

    scanf("%d%d", &m, &n);
    vec.eb(1, -1);
    vec.eb(n, -1);
    forn(i, 1, m) {
        scanf("%d%d%d%d", a + i, b + i, c + i, cost + i);
        cost[2 * m - i + 1] = cost[i];
        vec.eb(a[i], i);
        vec.eb(b[i], i + m);
        vec.eb(c[i], i + 2 * m);
    }

    sort(all(vec));
    int cnt = 0;
    forn(i, 0, sz(vec) - 1) {
        if (!i || vec[i].F != vec[i - 1].F) ++cnt;
        if (vec[i].S == -1) continue;
        if (vec[i].S <= m) a[vec[i].S] = cnt;
        else if (vec[i].S <= 2 * m) b[vec[i].S - m] = cnt;
        else c[vec[i].S - 2 * m] = cnt;
    }
    n = cnt;

    t[0].build(1, 1, n + 1);
    t[1].build(1, 1, n + 1);

    forn(i, 1, m) {
        d[i] = ool;
        if (a[i] == 1) d[i] = cost[i];
        /*forn(j, 1, i - 1) {
            if (a[i] <= c[j] && c[j] <= b[i]) d[i] = min(d[i], d[j] + cost[i]);
        }*/
        d[i] = min(t[0].get(1, 1, n + 1, a[i], b[i] + 1) + cost[i], d[i]);
        t[0].upd(1, 1, n + 1, c[i], c[i] + 1, d[i]);
        d[2 * m - i + 1] = d[i];
        a[2 * m - i + 1] = a[i];
        b[2 * m - i + 1] = b[i];
        c[2 * m - i + 1] = c[i];
    }
    forn(i, m + 1, 2 * m) {
        /*forn(j, m + 1, i - 1) {
            if (a[j] <= c[i] && c[i] <= b[j]) d[i] = min(d[i], d[j] + cost[i]);
        }*/
        d[i] = min(d[i], t[1].get(1, 1, n + 1, c[i], c[i] + 1) + cost[i]);
        t[1].upd(1, 1, n + 1, a[i], b[i] + 1, d[i]);
        if (b[i] == n) ans = min(ans, d[i]);
    }

    cout << (ans == ool ? -1 : ans) << "\n";

    return 0;
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:82:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &m, &n);
                          ^
pinball.cpp:86:57: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", a + i, b + i, c + i, cost + i);
                                                         ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 1 ms 428 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 496 KB Output is correct
6 Correct 2 ms 496 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 700 KB Output is correct
2 Correct 2 ms 700 KB Output is correct
3 Correct 2 ms 700 KB Output is correct
4 Correct 2 ms 704 KB Output is correct
5 Correct 2 ms 704 KB Output is correct
6 Correct 2 ms 704 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 704 KB Output is correct
2 Correct 2 ms 736 KB Output is correct
3 Correct 4 ms 864 KB Output is correct
4 Correct 4 ms 864 KB Output is correct
5 Correct 4 ms 1072 KB Output is correct
6 Correct 4 ms 1072 KB Output is correct
7 Correct 3 ms 1072 KB Output is correct
8 Correct 4 ms 1128 KB Output is correct
9 Correct 4 ms 1128 KB Output is correct
10 Correct 5 ms 1128 KB Output is correct

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3684 KB Output is correct
2 Correct 81 ms 6788 KB Output is correct
3 Correct 250 ms 16684 KB Output is correct
4 Correct 240 ms 16684 KB Output is correct
5 Correct 176 ms 21060 KB Output is correct
6 Correct 282 ms 22196 KB Output is correct
7 Correct 388 ms 40480 KB Output is correct
8 Correct 356 ms 40480 KB Output is correct
9 Correct 53 ms 40480 KB Output is correct
10 Correct 180 ms 43412 KB Output is correct
11 Correct 308 ms 67232 KB Output is correct
12 Correct 437 ms 71268 KB Output is correct
13 Correct 371 ms 75012 KB Output is correct
14 Correct 379 ms 78916 KB Output is correct