Submission #18074

#	Time	Username	Problem	Language	Result	Execution time	Memory
18074		tncks0121	Pinball (JOI14_pinball)	C++14	100 / 100	437 ms	33160 KiB

pinball

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