제출 #1331030

#제출 시각아이디문제언어결과실행 시간메모리
1331030viduxMi Teleférico (JOI25_ho_t3)C++17
0 / 100
828 ms37396 KiB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> pll;
const ll INF = 1e18;
int main() {
	ll n, m, p; cin >> n >> m >> p;
	vector<pair<ll, pll>> cab(m);
	for (int i = 0; i < m; i++) cin >> cab[i].second.first >> cab[i].second.second >> cab[i].first;
	sort(cab.begin(), cab.end());
	set<ll> sc;
	for (int i = 0; i < m; i++) sc.insert(cab[i].first);
	vl c(sc.begin(), sc.end());
	ll cl = 0, cr = 0;
	ll li = 0, ri = 0;
	ll alive = 0;
	vl in(n+1);
	map<ll, ll> mp;
	//for (auto i : c) cout << i << " "; cout << endl;
	while (li < m) {
		while (alive < n-1 && ri < m) {
			while (ri < m && cab[ri].first == c[cr]) {
				if (in[cab[ri].second.second] == 0) alive++;
				in[cab[ri].second.second]++;
				ri++;
			}
			cr++;
		}
		if (alive == n-1) mp[c[cl]] = c[cr-1];
		else mp[c[cl]] = INF;
		while (li < m && cab[li].first == c[cl]) {
			in[cab[li].second.second]--;
			if (in[cab[li].second.second] == 0) alive--;
			li++;
		}
		cl++;
	}
	ll mx = mp.begin()->second;
	ll q; cin >> q;
	vl ql(q), qr(q), qx(q);
	for (int i = 0; i < q; i++) {
		cin >> ql[i] >> qr[i] >> qx[i]; 
		if (!mp.count(ql[i])) mp[ql[i]] = 0;
	}
	for (auto &[l, r] : mp) { 
		mx = max(mx, r);
		r = max(mx, r);
	}
	for (int i = 0; i < q; i++) {
		ll l = ql[i], r = qr[i], x = qx[i];
		if (mp[l] <= r+x) cout << "Yes\n";
		else cout << "No\n";
	}
	cout << endl;
}
// Test of idea. Only Sub1
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...