Submission #316341

#	Time	Username	Problem	Language	Result	Execution time	Memory
316341		CodeTiger927	Pinball (JOI14_pinball)	C++14	100 / 100	850 ms	141944 KiB

pinball

using namespace std;

#include <iostream>

#define MAXN 100005

using namespace std;

struct node {
    int l, r;
    long long v;
    node *c[2];
    node(int l, int r) : l{l}, r{r} {
        v = 1e17;
        c[0] = nullptr;
        c[1] = nullptr;
    } 
    void upd(int x,long long v) {
        this -> v = min(this -> v,v);
        if (l != r) {
            int m = l + (r - l) / 2;
            if (x <= m) {
                if (!c[0]) c[0] = new node(l, m);
                c[0] -> upd(x, v);
            } else {
                if (!c[1]) c[1] = new node(m + 1, r);
                c[1] -> upd(x, v);
            }
        }
    }
    long long qry(int x, int y) {
        if (x <= l && r <= y) return v;
        if (y < l || x > r) return 1e17;
        long long res = 1e17;
        if (c[0]) res = min(res,c[0] -> qry(x, y));
        if (c[1]) res = min(res,c[1] -> qry(x, y));
        return res;
    }
};

int qa[MAXN],qb[MAXN],qc[MAXN],M,N;
long long arr[MAXN];

long long solve() {
	node *st1 = new node(1,1000000000);
	node *st2 = new node(1,1000000000);

	long long ans = 1e17;
	st1 -> upd(1,0);
	st2 -> upd(N,0);

	for(int i = 0;i < M;++i) {
		long long nv1 = st1 -> qry(qa[i],qb[i]);
		long long nv2 = st2 -> qry(qa[i],qb[i]);
		st1 -> upd(qc[i],nv1 + arr[i]);
		st2 -> upd(qc[i],nv2 + arr[i]);
		ans = min(ans,nv1 + nv2 + arr[i]);
	}
	return ans;
}

int main() {
	cin >> M >> N;
	for(int i = 0;i < M;++i) {
		cin >> qa[i] >> qb[i] >> qc[i] >> arr[i];
	}
	long long ans = solve();
	if(ans == 1e17) {
		cout << -1 << endl;
	}else{
		cout << ans << endl;
	}
}

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