oj.uz

Submission #18072

# Submission time Handle Problem Language Result Execution time Memory
18072 2016-01-19T15:24:39 Z tncks0121 Pinball (JOI14_pinball) C++14
51 / 100
 384 ms 24964 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <deque>
#include <utility>
#include <bitset>
#include <limits.h>
#include <time.h>
#include <functional>
#include <numeric>
 
using namespace std;
typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int M_ = 100500;
const ll oo = (ll)1e18;

int M, N, X;
struct device {
    int a, b, c, d;
};
device devices[M_];

    const int LEAF = 131072 * 2;
    const int TSZ = LEAF + LEAF + 2;

struct minSegmentTree {
    ll tree[TSZ];

    minSegmentTree() { fill(tree, tree + TSZ, oo); }

    void upd (int x, ll v) {
        x += LEAF;
        while(x > 0) {
            tree[x] = min(tree[x], v);
            x >>= 1;
        }
    }

    ll get (int x, int y) {
        ll ret = oo;
        x += LEAF; y += LEAF;
        while(x <= y) {
            if((x & 1) == 1) ret = min(ret, tree[x]);
            if((y & 1) == 0) ret = min(ret, tree[y]);
            x = (x + 1) >> 1;
            y = (y - 1) >> 1;
        }
        return ret;
    }
};

minSegmentTree tree[2]; 
map<int, int> ren;

int main() {
    scanf("%d%d", &M, &N);
    for(int i = 1; i <= M; i++) {
        device &d = devices[i];
        scanf("%d%d%d%d", &d.a, &d.b, &d.c, &d.d);
        ren[d.a] = -1;
        ren[d.b] = -1;
        ren[d.c] = -1;
    }
    ren[1] = -1;
    ren[N] = -1;

    {
        int v = 0;
        for(auto &it : ren) it.second = ++v;
        for(int i = 1; i <= M; i++) {
            device &d = devices[i];
            d.a = ren[d.a];
            d.b = ren[d.b];
            d.c = ren[d.c];
        }
        X = ren[N];
    }


    ll ans = oo;
    tree[0].upd(1, 0);
    tree[1].upd(X, 0);

    for(int i = 1; i <= M; i++) {
        device &d = devices[i];

        ll v[2] = {oo, oo};
        for(int t = 0; t < 2; t++) {
            v[t] = tree[t].get(d.a, d.b);
            if(v[t] < oo) {
                v[t] += d.d;
                tree[t].upd(d.c, v[t]);
            }
        }

        if(v[0] < oo && v[1] < oo) {
            ans = min(ans, v[0] + v[1] - d.d);
        }
    }

    if(ans >= oo) ans = -1;
    printf("%lld\n", ans);


    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
0.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 11768 KB Output is correct
2 Correct 42 ms 13484 KB Output is correct
3 Correct 194 ms 15728 KB Output is correct
4 Correct 136 ms 10976 KB Output is correct
5 Correct 168 ms 15200 KB Output is correct
6 Correct 237 ms 11768 KB Output is correct
7 Correct 384 ms 18764 KB Output is correct
8 Correct 339 ms 16520 KB Output is correct
9 Correct 33 ms 13616 KB Output is correct
10 Correct 183 ms 17972 KB Output is correct
11 Runtime error 221 ms 24964 KB Program hung waiting for input
12 Halted 0 ms 0 KB -