Submission #29800

#	Time	Username	Problem	Language	Result	Execution time	Memory
29800		cdemirer	Pinball (JOI14_pinball)	C++14	100 / 100	843 ms	378584 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;
typedef vector<vector<pair<int, int> > > vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

const int maxn = 1073741823;

int M, N;
int A[100000], B[100000], C[100000], D[100000];

typedef struct Node_ {
	int l, r, p;
	ll lval, rval;
} Node;
Node rez[12000001];
int rezcnt = 1;
int root;

int createNode() {
	rez[rezcnt].l = rez[rezcnt].r = rez[rezcnt].p = 0;
	rez[rezcnt].lval = rez[rezcnt].rval = -1;
	return rezcnt++;
}

void push(int x) {
	int l = rez[x].l;
	int r = rez[x].r;
	if (!l) l = rez[x].l = createNode();
	rez[l].p = x;
	if (!r) r = rez[x].r = createNode();
	rez[r].p = x;
}
void refresh(int x) {
	x = rez[x].p;
	int l = rez[x].l, r = rez[x].r;
	if (!l) l = rez[x].l = createNode();
	if (!r) r = rez[x].r = createNode();
	while (x) {
		ll a = rez[rez[x].l].lval, b = rez[rez[x].r].lval;
		ll c = rez[rez[x].l].rval, d = rez[rez[x].r].rval;
		if (a == -1) rez[x].lval = b;
		else if (b == -1) rez[x].lval = a;
		else rez[x].lval = min(a, b);
		if (c == -1) rez[x].rval = d;
		else if (d == -1) rez[x].rval = c;
		else rez[x].rval = min(c, d);
		x = rez[x].p;
	}
}
ll lget(int x, int l, int r, int cl, int cr) {
	if (cl != cr) push(x);
	int cmid = (cl+cr)/2;
	if (l == cl && r == cr) return rez[x].lval;
	else if (r <= cmid) return lget(rez[x].l, l, r, cl, cmid);
	else if (l > cmid) return lget(rez[x].r, l, r, cmid+1, cr);
	else {
		ll a = lget(rez[x].l, l, cmid, cl, cmid);
		ll b = lget(rez[x].r, cmid+1, r, cmid+1, cr);
		if (a == -1) return b;
		else if (b == -1) return a;
		else return min(a, b);
	}
}
ll rget(int x, int l, int r, int cl, int cr) {
	if (cl != cr) push(x);
	int cmid = (cl+cr)/2;
	if (l == cl && r == cr) return rez[x].rval;
	else if (r <= cmid) return rget(rez[x].l, l, r, cl, cmid);
	else if (l > cmid) return rget(rez[x].r, l, r, cmid+1, cr);
	else {
		ll a = rget(rez[x].l, l, cmid, cl, cmid);
		ll b = rget(rez[x].r, cmid+1, r, cmid+1, cr);
		if (a == -1) return b;
		else if (b == -1) return a;
		else return min(a, b);
	}
}
void updatel(int x, int p, int cl, int cr, ll u) {
	if (cl != cr) push(x);
	int cmid = (cl+cr)/2;
	if (p == cl && p == cr) {
		if (rez[x].lval == -1) rez[x].lval = u;
		else rez[x].lval = min(rez[x].lval, u);
		refresh(x);
	}
	else if (p <= cmid) updatel(rez[x].l, p, cl, cmid, u);
	else if (p > cmid) updatel(rez[x].r, p, cmid+1, cr, u);
}
void updater(int x, int p, int cl, int cr, ll u) {
	if (cl != cr) push(x);
	int cmid = (cl+cr)/2;
	if (p == cl && p == cr) {
		if (rez[x].rval == -1) rez[x].rval = u;
		else rez[x].rval = min(rez[x].rval, u);
		refresh(x);
	}
	else if (p <= cmid) updater(rez[x].l, p, cl, cmid, u);
	else if (p > cmid) updater(rez[x].r, p, cmid+1, cr, u);
}

int main(int argc, char **argv) {

	//freopen("input", "r", stdin);
	//freopen("output", "w", stdout);

	scanf("%d%d", &M, &N);
	for (int i = 0; i < M; i++) {
		scanf("%d%d%d%d", &(A[i]), &(B[i]), &(C[i]), &(D[i]));
		A[i]--; B[i]--; C[i]--;
	}

	root = createNode();
	updatel(root, 0, 0, maxn, 0);
	updater(root, N-1, 0, maxn, 0);
	ll ans = (ll)1e18;

	for (int i = 0; i < M; i++) {
		ll a = lget(root, A[i], B[i], 0, maxn);
		ll b = rget(root, A[i], B[i], 0, maxn);
		if (a != -1) {
			updatel(root, C[i], 0, maxn, a+D[i]);
		}
		if (b != -1) {
			updater(root, C[i], 0, maxn, b+D[i]);
		}
		if (a != -1 && b != -1) {
			ans = min(ans, a+b+D[i]);
		}
	}
	if (ans == (ll)1e18) puts("-1");
	else printf("%lld\n", ans);

	return 0;
}

Compilation message (stderr)

pinball.cpp: In function 'int main(int, char**)':
pinball.cpp:112:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &M, &N);
                       ^
pinball.cpp:114:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &(A[i]), &(B[i]), &(C[i]), &(D[i]));
                                                        ^

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