Submission #95237

#	Time	Username	Problem	Language	Result	Execution time	Memory
95237		shoemakerjo	Pinball (JOI14_pinball)	C++14	100 / 100	861 ms	200028 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

int M, N; //N is up to 10^9 
const int maxm = 100010;
using ll = long long;

int a[maxm];
int b[maxm];
int c[maxm];
ll d[maxm];
const ll inf = 1e18;

//let's just do dynamic

struct node {
	ll val;
	node *left;
	node *right;
	node (ll vv, node *ll, node *rr) :
		val(vv), left(ll),  right(rr) {}
	node *insert(int spot, ll val, int ss, int se);
};

node *null = new node(inf, NULL, NULL);

node *leftroot;
node *rightroot;

node *node::insert(int spot, ll val, int ss , int se) {
	if (ss == se) {
		return new node(min(this->val, val), null, null);
	}
	int mid = (ss+se)/2;
	if (spot <= mid) {
		return new node(min(this->val, val),
			this->left->insert(spot, val, ss, mid),
			this->right);
	}
	return new node(min(this->val, val),
		this->left, 
		this->right->insert(spot, val, mid+1, se));
}

ll query(node *cur, int qs, int qe, int ss = 1, int se = N) {
	if (qs > qe || ss > se || qs > se || qe < ss) return inf;
	if (qs <= ss && se <= qe) return cur->val;
	int mid = (ss+se)/2;
	return min(query(cur->left, qs, qe, ss, mid),
		query(cur->right, qs, qe, mid+1, se));
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	null->right = null;
	null->left = null;
	//1 device for each row
	cin >> M >> N;
	for (int i = 1; i <= M; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	leftroot = new node(inf, null, null);
	rightroot = new node(inf, null, null);

	leftroot = leftroot->insert(1, 0, 1, N);
	rightroot = rightroot->insert(N, 0, 1, N);

	ll ans = inf;
	for (int i = 1; i <= M; i++) {
		ll cl; //get to my left endpoint
		ll cr; //get to my right endpoint

		cl = query(leftroot, a[i], N);
		cr = query(rightroot, 1, b[i]);

		ans = min(ans, cl + cr + d[i]);

		// cout << "updating " << c[i] << " : " << 
		// 	cl+d[i] << " - " << cr + d[i] << endl;

		leftroot = leftroot->insert(c[i], cl + d[i], 1, N);
		rightroot = rightroot->insert(c[i], cr + d[i], 1, N);
	}
	if (ans >= inf) cout << -1 << endl;
	else cout << ans << endl;

}

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