Submission #871373

#	Time	Username	Problem	Language	Result	Execution time	Memory
871373		serifefedartar	Pinball (JOI14_pinball)	C++17	100 / 100	337 ms	22516 KiB

pinball

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9+9;
const ll LOGN = 22; 
const ll MAXN = 4e5 + 100;

vector<int> cc;
struct Machine {
	int l, r, centr;
	ll cost;
	void read() {
		cin >> l >> r >> centr >> cost;
		cc.push_back(l);
		cc.push_back(r);
		cc.push_back(centr);
	}
	Machine(int _l, int _r, int _centr, ll _cost) : l(_l), r(_r), centr(_centr), cost(_cost) { }
	Machine() { }
};

vector<Machine> v;
int n;
ll sg[4*MAXN], to_right[MAXN], to_left[MAXN];
void init(int k, int a, int b) {
	if (a == b) {
		sg[k] = 1e16;
		return ;
	}
	init(2*k, a, (a+b)/2);
	init(2*k+1, (a+b)/2+1, b);
	sg[k] = min(sg[2*k], sg[2*k+1]);
}

void update(int k, int a, int b, int plc, ll val) {
	if (b < plc || a > plc)
		return ;
	if (a == b) {
		sg[k] = min(sg[k], val);
		return ;
	}
	update(2*k, a, (a+b)/2, plc, val);
	update(2*k+1, (a+b)/2+1, b, plc, val);
	sg[k] = min(sg[2*k], sg[2*k+1]);
}

ll query(int k, int a, int b, int q_l, int q_r) {
	if (q_l > b || q_r < a)
		return 1e16;
	if (q_l <= a && b <= q_r)
		return sg[k];
	return min(query(2*k, a, (a+b)/2, q_l, q_r),
				query(2*k+1, (a+b)/2+1, b, q_l, q_r));
}

int index(int k) {
	return lower_bound(cc.begin(), cc.end(), k) - cc.begin();
}

int main() {
	int M, N;
	cin >> M >> N;

	v = vector<Machine>(M+1);
	for (int i = 1; i <= M; i++)
		v[i].read();
	sort(cc.begin(), cc.end());
	cc.erase(unique(cc.begin(), cc.end()), cc.end());
	n = cc.size();

	init(1, 1, n);
	for (int i = 1; i <= M; i++) {
		ll Q = query(1, 1, n, index(v[i].l), index(v[i].r));
		if (v[i].l == 1)
			Q = 0;

		to_left[i] = Q + v[i].cost;
		update(1, 1, n, index(v[i].centr), to_left[i]);
	}

	init(1, 1, n);
	for (int i = 1; i <= M; i++) {
		ll Q = query(1, 1, n, index(v[i].l), index(v[i].r));
		if (v[i].r == N)
			Q = 0;

		to_right[i] = Q + v[i].cost;
		update(1, 1, n, index(v[i].centr), to_right[i]);
	}

	ll mn = 1e16;
	for (int i = 1; i <= M; i++)
		mn = min(mn, to_left[i] + to_right[i] - v[i].cost);

	if (mn >= 1e14)
		mn = -1;
	cout << mn << "\n";
}

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