Submission #1331210

#TimeUsernameProblemLanguageResultExecution timeMemory
1331210viduxMi Teleférico (JOI25_ho_t3)C++17
49 / 100
2095 ms89476 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;
struct Node {
	ll l = 0, r = INF;
	ll nxl = 0, nxr = 0;
	ll v = INF;
};
vector<Node> t(1);
ll query(ll ql, ll qr, int id = 0) {
	ll l = t[id].l, r = t[id].r;
	if (ql <= l && r <= qr) return t[id].v;
	if (ql >= r || l >= qr) return INF;
	ll vl = t[id].nxl ? query(ql, qr, t[id].nxl) : INF;
	ll vr = t[id].nxr ? query(ql, qr, t[id].nxr) : INF;
	return min(vl, vr);
}
void update(ll p, ll v, int id = 0) {
	ll l = t[id].l, r = t[id].r;
	if (p < l || p >= r) return;
	if (r-l == 1) {
		t[id].v = v;
		return;
	}
	ll m = (l+r)/2;
	if (p < m && !t[id].nxl) t[id].nxl = (ll)t.size(), t.push_back(Node{l, m});
	if (p >= m && !t[id].nxr) t[id].nxr = (ll)t.size(), t.push_back(Node{m, r});
	if (p < m) update(p, v, t[id].nxl);
	if (p >= m) update(p, v, t[id].nxr);
	ll vl = t[id].nxl ? t[t[id].nxl].v : INF;
	ll vr = t[id].nxr ? t[t[id].nxr].v : INF;
	t[id].v = min(vl, vr);
}
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);
	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;
		update(it->first, -(it->first)+(it->second));
		//cout << it->first << " " << it->second << endl;
	}
	for (int i = 0; i < q; i++) {
		ll l = ql[i], r = qr[i], x = qx[i];
		bool ok = 0;
		ll mn = query(max(0ll, l-x), 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...