oj.uz

답안 #18074

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18074 2016-01-19T15:33:17 Z tncks0121 Pinball (JOI14_pinball) C++14
100 / 100
 437 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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 19168 KB Output is correct
2 Correct 0 ms 19168 KB Output is correct
3 Correct 4 ms 19168 KB Output is correct
4 Correct 0 ms 19168 KB Output is correct
5 Correct 4 ms 19168 KB Output is correct
6 Correct 4 ms 19168 KB Output is correct
7 Correct 0 ms 19168 KB Output is correct
8 Correct 2 ms 19168 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 19168 KB Output is correct
2 Correct 0 ms 19168 KB Output is correct
3 Correct 2 ms 19168 KB Output is correct
4 Correct 5 ms 19168 KB Output is correct
5 Correct 0 ms 19168 KB Output is correct
6 Correct 0 ms 19168 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 19168 KB Output is correct
2 Correct 5 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 6 ms 19168 KB Output is correct
6 Correct 0 ms 19168 KB Output is correct
7 Correct 3 ms 19168 KB Output is correct
8 Correct 0 ms 19300 KB Output is correct
9 Correct 6 ms 19300 KB Output is correct
10 Correct 3 ms 19300 KB Output is correct

Subtask #4
49.0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 19960 KB Output is correct
2 Correct 69 ms 21676 KB Output is correct
3 Correct 193 ms 23920 KB Output is correct
4 Correct 162 ms 19168 KB Output is correct
5 Correct 154 ms 23392 KB Output is correct
6 Correct 225 ms 19960 KB Output is correct
7 Correct 377 ms 26956 KB Output is correct
8 Correct 335 ms 24712 KB Output is correct
9 Correct 37 ms 21808 KB Output is correct
10 Correct 196 ms 26164 KB Output is correct
11 Correct 237 ms 33160 KB Output is correct
12 Correct 437 ms 33160 KB Output is correct
13 Correct 365 ms 33160 KB Output is correct
14 Correct 333 ms 33160 KB Output is correct