Submission #1033281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033281		zaza	Pinball (JOI14_pinball)	C++14	0 / 100	0 ms	344 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct Seg{
	
	int n;
	
	vector<long long> s;
	
	Seg(int _n = 0): n(_n) {
		s.resize(4 << __lg(n), 2e18);
	}
	
	void upd(int i, long long v) {
		
		int l = 1, r = n, id = 1;
		
		while (l < r) {
			int mid = (l + r) / 2;
			id *= 2;
			
			if (i <= mid) {
				r = mid;
			} else {
				l = mid + 1;
				id++;
			}
			
		}
		
		s[id] = min(s[id], v);
		
		while (id > 1) {
			id /= 2;	
			s[id] = min(s[id * 2], s[id * 2 + 1]);
		}
	}
	
	long long get(int i, int j, int id, int l, int r) {
		
		if (i <= l && r <= j) {
			return s[id];
		}
		
		int mid = (l + r) / 2;
		
		if (i <= mid && mid < j) {
			return min(get(i, j, id * 2, l, mid), get(i, j, id * 2 + 1, mid + 1, r));
		}
		
		if (mid < i) {
			return get(i, j, id * 2 + 1, mid + 1, r);
		}
		
		return get(i, j, id * 2, l, mid);		
	}
	
	long long get(int i, int j) {
		return get(i, j, 1, 1, n);
	}
};

int m, n;

int a[100005], b[100005], c[100005], d[100005];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> m >> n;
	
	vector<int> val;
	
	for (int i = 1; i <= m; ++i) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
		
		val.emplace_back(a[i]);
		val.emplace_back(b[i]);
		val.emplace_back(c[i]);
	}
	
	sort(val.begin(), val.end());
	
	val.erase(unique(val.begin(), val.end()), val.end());
	
	for (int i = 1; i <= m; ++i) {
		a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1;
		b[i] = lower_bound(val.begin(), val.end(), b[i]) - val.begin() + 1;
		c[i] = lower_bound(val.begin(), val.end(), c[i]) - val.begin() + 1;
		
		//cout << a[i] << ' ' << b[i] << ' ' << c[i] << '\n';
	}
	
	Seg ST1((int)val.size()), ST2((int)val.size());
	
	long long ans = 2e18;
	
	for (int i = 1; i <= m; ++i) {
		
		long long k1 = ST1.get(a[i], b[i]);
		long long k2 = ST2.get(a[i], b[i]);
		
		if (max(k1, k2) < 2e18) {
			ans = min(ans, k1 + k2 + d[i]);
		}
		
		if (val[a[i] - 1] == 1 && val[b[i] - 1] == n) {
			ans = min(ans, 1ll * d[i]);
		}
		
		if (val[a[i] - 1] == 1) {
			ST1.upd(c[i], d[i]);
		} else {
			
			if (k1 < 2e18) {
				ST1.upd(c[i], k1 + d[i]);
			}
		}
		
		if (val[b[i] - 1] == n) {
			ST2.upd(c[i], d[i]);
		} else {
			
			if (k2 < 2e18) {
				ST2.upd(c[i], k2 + d[i]);
			}
		}
	}
	
	if (ans < 2e18) {
		cout << ans;
	} else {
		cout << "-1";
	}
}

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