oj.uz

Submission #18073

# Submission time Handle Problem Language Result Execution time Memory
18073 2016-01-19T15:25:23 Z tncks0121 Pinball (JOI14_pinball) C++14
100 / 100
 458 ms 33160 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 * 4;
    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 5 ms 19168 KB Output is correct
2 Correct 0 ms 19168 KB Output is correct
3 Correct 5 ms 19168 KB Output is correct
4 Correct 4 ms 19168 KB Output is correct
5 Correct 2 ms 19168 KB Output is correct
6 Correct 0 ms 19168 KB Output is correct
7 Correct 4 ms 19168 KB Output is correct
8 Correct 0 ms 19168 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 19960 KB Output is correct
2 Correct 62 ms 21676 KB Output is correct
3 Correct 226 ms 23920 KB Output is correct
4 Correct 139 ms 19168 KB Output is correct
5 Correct 150 ms 23392 KB Output is correct
6 Correct 242 ms 19960 KB Output is correct
7 Correct 345 ms 26956 KB Output is correct
8 Correct 337 ms 24712 KB Output is correct
9 Correct 42 ms 21808 KB Output is correct
10 Correct 166 ms 26164 KB Output is correct
11 Correct 203 ms 33160 KB Output is correct
12 Correct 458 ms 33160 KB Output is correct
13 Correct 377 ms 33160 KB Output is correct
14 Correct 276 ms 33160 KB Output is correct