제출 #1291462

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1291462		Jawad_Akbar_JJ	Pinball (JOI14_pinball)	C++20	100 / 100	425 ms	58384 KiB

pinball

#include <iostream>
#include <map>

using namespace std;
#define int long long
const int N = (1<<19) + 1, inf = 1e17;
int Mn[2][N<<1], a[N], b[N], c[N], d[N], Mem[N], cur;
map<int,int> mp, mp2;

void insert(int t, int i, int vl, int cur = 1, int st = 1, int en = N){
	if (i >= en or i < st)
		return;
	Mn[t][cur] = min(Mn[t][cur], vl);
	if (en - st == 1)
		return;
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;

	insert(t, i, vl, lc, st, mid);
	insert(t, i, vl, rc, mid, en);
}

int get(int t, int l, int r, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return inf;
	if (l <= st and r >= en)
		return Mn[t][cur];
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	return min(get(t, l, r, lc, st, mid), get(t, l, r, rc, mid, en));
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	for (int i=1;i<(N<<1);i++)
		Mn[0][i] = Mn[1][i] = inf;

	int m, n;
	cin>>m>>n;

	for (int i=1;i<=m;i++){
		cin>>a[i]>>b[i]>>c[i]>>d[i];
		mp[a[i]] = mp[b[i]] = mp[c[i]] = 1;
	}

	if (mp[1] == 0 or mp[n] == 0)
		return cout<<-1<<'\n', 0;

	for (auto [i, j] : mp)
		mp2[i] = ++cur;

	insert(0, 1, 0);
	for (int i=1;i<=m;i++){
		a[i] = mp2[a[i]];
		b[i] = mp2[b[i]];
		c[i] = mp2[c[i]];

		Mem[i] = get(0, a[i], cur + 1) + d[i];

		insert(0, c[i], Mem[i]);
	}

	for (int i=m;i>=1;i--){
		Mem[i] = min(Mem[i], get(1, c[i], cur + 1) + d[i]);

		insert(1, b[i], Mem[i]);
	}

	int Ans = get(1, cur, cur + 1);
	if (Ans == inf)
		Ans = -1;
	cout<<Ans<<'\n';
}

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