Submission #1033519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033519		vjudge1	Pinball (JOI14_pinball)	C++14	100 / 100	146 ms	19660 KiB

pinball

#include <bits/stdc++.h>

using namespace std;

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];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> m >> n;
	
	vector<int> val;
	
	val.emplace_back(1);
	val.emplace_back(n);
	
	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';
	}
	
	int t = val.size();
	
	Seg ST1(t), ST2(t);
	
	long long ans = 2e18;
	
	ST1.upd(1, 0);
	ST2.upd(t, 0);
	
	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 (k1 < 2e18) {
			ST1.upd(c[i], k1 + d[i]);
		}
		
		if (k2 < 2e18) {
			ST2.upd(c[i], k2 + d[i]);
		}
	}
	
	if (ans < 2e18) {
		cout << ans << '\n';
	} else {
		cout << "-1\n";
	}
}

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