Submission #1040222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1040222		Hamed_Ghaffari	Pinball (JOI14_pinball)	C++17	0 / 100	1 ms	6616 KiB

pinball

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int,int>;

#define X first
#define Y second
#define SZ(x) int(x.size())
#define mins(a, b) (a = min(a, b))
#define lc id<<1
#define rc lc|1
#define mid ((l+r)/2)
#define pb push_back
#define all(x) x.begin(), x.end()

const int MXN = 3e5 + 5;
const int MOD = 1e9 + 7;
const ll  INF = 2e18;

int n, m, a[MXN], b[MXN], c[MXN], d[MXN];
vector<int> cmp;

inline int GI(int x) {
	return lower_bound(all(cmp), x)-cmp.begin();
}

int N;
ll seg[2][MXN<<2];
void Build(int l=0, int r=N, int id=1) {
	if(r-l == 1) {
		seg[0][id] = seg[1][id] = INF;
		return;
	}
	Build(l, mid, lc);
	Build(mid, r, rc);
	seg[0][id] = min(seg[0][lc], seg[0][rc]);
	seg[1][id] = min(seg[1][lc], seg[1][rc]);
}
void Upd(int ind, int p, ll x, int l=0, int r=N, int id=1) {
	if(r-l == 1) {
		mins(seg[ind][id], x);
		return;
	}
	if(p<mid) Upd(ind, p, x, l, mid, lc);
	else Upd(ind, p, x, mid, r, rc);
	seg[ind][id] = min(seg[ind][lc], seg[ind][rc]); 
}
ll Get(int ind, int s, int e, int l=0, int r=N, int id=1) {
	if(s<=l && r<=e) return seg[ind][id];
	if(e<=mid) return Get(ind, s, e, l, mid, lc);
	if(s>=mid) return Get(ind, s, e, mid, r, rc);
	return min(Get(ind, s, e, l, mid, lc), Get(ind, s, e, mid, r, rc));
}

int32_t main() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> m >> n;
	for(int i=1; i<=m; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		cmp.pb(a[i]);
		cmp.pb(b[i]);
		cmp.pb(c[i]);
	}
	sort(all(cmp));
	cmp.resize(unique(all(cmp))-cmp.begin());
	N = SZ(cmp);
	Build();
	Upd(0, 0, 0);
	Upd(1, N-1, 0);
	ll ans=INF;
	for(int i=1; i<=n; i++) {
		a[i] = GI(a[i]);
		b[i] = GI(b[i]);
		c[i] = GI(c[i]);
		ll c1 = Get(0, a[i], b[i]+1), c2 = Get(1, a[i], b[i]+1);
		if(c1<INF && c2<INF)
			mins(ans, c1+c2+d[i]);
		else if(c1<INF) Upd(0, c[i], c1+d[i]);
		else if(c2<INF) Upd(1, c[i], c2+d[i]);
	}
	cout << (ans<INF ? ans : -1) << '\n';
	return 0;
}

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