Submission #1331217

#TimeUsernameProblemLanguageResultExecution timeMemory
1331217viduxMi Teleférico (JOI25_ho_t3)C++17
19 / 100
960 ms74504 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 m = 0;
vl t;
ll query (int l, int r) {
	ll res = INF;
	for (l += m, r += m; l < r; l /= 2, r /= 2) {
		if (l&1) res = min(res, t[l++]);
		if (r&1) res = min(res, t[--r]);
	}
	return res;
}
void update(ll p, ll v) {
	for (t[p += m] = v; p > 1; p /= 2) t[p/2] = min(t[p], t[p^1]);
}
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 = INF;
	ll q; cin >> q;
	vl ql(q), qr(q), qx(q);
	if (!mp.count(0)) mp[0] = 0;
	for (int i = 0; i < q; i++) {
		cin >> ql[i] >> qr[i] >> qx[i]; 
		if (!mp.count(ql[i])) mp[ql[i]] = 0;
		if (!mp.count(ql[i]-qx[i])) mp[ql[i]-qx[i]] = 0;
	}
	for (auto it = mp.rbegin(); it != mp.rend(); it++) { 
		if (it->second) mx = min(mx, it->second);
		else it->second = mx;
		//cout << it->first << " " << it->second << endl;
	}
	unordered_map<ll, ll> conv;
	for (auto [x, y] : mp) conv[x] = m++;
	t = vl(m*2, INF);
	for (auto [x, y] : mp) update(conv[x], -x+y);
	for (int i = 0; i < q; i++) {
		ll l = ql[i], r = qr[i], x = qx[i];
		bool ok = 0;
		ll mn = query(conv[max(0ll, l-x)], conv[l]+1);
		ok |= mp[l] <= r+x;
		ok |= mp[l-x] <= r;
		ok |= mn <= x+r-l;
		if (ok) cout << "Yes\n";
		else cout << "No\n";
	}
	cout << endl;
}
#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...