Submission #1331281

#TimeUsernameProblemLanguageResultExecution timeMemory
1331281viduxMi Teleférico (JOI25_ho_t3)C++17
80 / 100
2054 ms119672 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() {
	ios::sync_with_stdio(0); cin.tie(0);
	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());
	vl c;
	c.reserve(m);
	for (auto [ci, ab] : cab) if (!c.size() || (c.size() && c.back() != ci)) c.push_back(ci);
	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);
	mp[0] = max(mp[0], 0ll);
	for (int i = 0; i < q; i++) {
		cin >> ql[i] >> qr[i] >> qx[i]; 
		mp[ql[i]] = max(0ll, mp[ql[i]]);
		mp[ql[i]-qx[i]] = max(0ll, mp[ql[i]-qx[i]]);
	}
	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;
	}
	vl xs; xs.reserve(mp.size());
	for (auto [k, v] : mp) xs.push_back(k);
	vl f(xs.size());
	for (int i = 0; i < xs.size(); i++) f[i] = mp[xs[i]];
	auto idx = [&](ll x) -> ll {
		return lower_bound(xs.begin(), xs.end(), x)-xs.begin();
	};
	M = xs.size();
	t.assign(2*M, INF);
	for (int i = 0; i < M; i++) t[M+i] = f[i]-xs[i];
	for (int i = M-1; i >= 1; i--) t[i] = min(t[i*2], t[i*2+1]);
	for (int i = 0; i < q; i++) {
		ll l = ql[i], r = qr[i], x = qx[i];
		ll lx = max(0LL, l-x);
		int idl = idx(l);
		int idlx = idx(lx);
		bool ok = 0;
		ok |= f[idl] <= r+x;
		ok |= f[idlx] <= r;
		ok |= query(idlx, idl+1) <= r+x-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...