제출 #53872

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
53872		MladenP	Pinball (JOI14_pinball)	C++17	51 / 100	1084 ms	3352 KiB

pinball

#include<bits/stdc++.h>
#define STIZE(x) fprintf(stderr, "STIZE%lld\n", x);
#define PRINT(x) fprintf(stderr, "%s = %lld\n", #x, x);
#define NL(x) printf("%c", " \n"[(x)]);
#define lld long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
#define all(a) begin(a),end(a)
#define sz(a) int((a).size())
#define LINF 1000000000000000LL
#define INF 1000000000
#define EPS 1e-9
using namespace std;
#define MAXN 100010
struct SegNode{
    int L, R;
    lld val;
    SegNode *left, *right;
    SegNode() { L = R = val = 0; left = right = NULL; }
    SegNode(int _L, int _R, lld _val) { L = _L, R = _R, val = _val; left = right = NULL; }
    void update(int idx, lld upd) {
        //printf("%d %d\n", L, R);
        if(L == R) {
            val = min(val, upd);
            return;
        }
        int mid = (L+R)/2;
        if(idx <= mid) {
            if(left == NULL) left = new SegNode(L, mid, LINF);
            left->update(idx, upd);
        } else {
            if(right == NULL) right = new SegNode(mid+1, R, LINF);
            right->update(idx, upd);
        }
        val = min((left != NULL ? left->val:LINF), (right != NULL ? right->val:LINF));
    }
    lld sum(int l, int r) {
        if(l <= L && R <= r) {
            return val;
        }
        int mid = (L+R)/2;
        lld rez = LINF;
        if(L <= mid) rez = min(rez, (left == NULL ? LINF:left->sum(l, r)));
        if(R > mid) rez = min(rez, (right == NULL ? LINF:right->sum(l, r)));
        return rez;
    }
};
lld a[MAXN], b[MAXN], c[MAXN], d[MAXN];
lld dpl[MAXN], dpr[MAXN];
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int m, n; cin >> m >> n;
    SegNode* segtreeL = new SegNode(1, n, LINF);
    SegNode* segtreeR = new SegNode(1, n, LINF);
    segtreeL->update(1, 0);
    segtreeR->update(n, 0);
    lld rez = LINF;
    for(int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        dpl[i] = segtreeL->sum(a[i], b[i]) + d[i];
        dpr[i] = segtreeR->sum(a[i], b[i]) + d[i];
        //PRINT(i);
        //PRINT(dpl[i]);
        //PRINT(dpr[i]);
        rez = min(rez, dpl[i]+dpr[i]-d[i]);

        segtreeL->update(c[i], dpl[i]);
        segtreeR->update(c[i], dpr[i]);
    }
    cout << (rez == LINF ? -1:rez);
    return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 0 / 49