81分鑪关求条
查看原帖
81分鑪关求条
482315
lovely_nst楼主2025/2/5 21:00
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n , m , p , q;
const int N = 4e5 + 5 , inf = 0x7f7f7f7f7f7f7f7f;
vector <int> s , a[N] , g[N];
int d[4 * N] , R[N] , f[N][21] , lg[N];
void update (int l , int c , int s , int t , int p)
{
	if (s == t)
  	{
    	d[p] = c;
    	return;
  	}
	int m = s + t >> 1;
	if (l <= m) update (l , c , s , m , p << 1);
	if (l > m) update (l , c , m + 1 , t , p << 1 | 1);
	d[p] = min (d[p << 1] , d[p << 1 | 1]);
}
int getmax (int l , int r)
{
	int fl = lower_bound (s.begin () , s.end () , l) - s.begin () + 1 , fr = lower_bound (s.begin () , s.end () , r) - s.begin () + 1;
	if (fl == fr)
		return r - R[fr - 1];
	int Lg = lg[fr - fl];
	return max (max (f[fl][Lg] , f[fr - (1 << Lg)][Lg]) , r - R[fr - 1]);
}
signed main ()
{
	ios::sync_with_stdio (0) , cin.tie (0) , cout.tie (0);
	cin >> n >> m >> p;
	for (int i = 1;i <= m;i ++)
	{
		int v , w;
		cin >> v >> v >> w;
		g[v].push_back (w);
		s.push_back (w);
	}
	sort (s.begin () , s.end ()) , unique (s.begin () , s.end ());
	for (int i = 1;i <= n;i ++)
		for (int j : g[i])
			a[lower_bound (s.begin () , s.end () , j) - s.begin ()].push_back (i);
	int l = 0 , p = s.size ();
	memset (R , 0x7f , sizeof R);
	memset (d , -1 , sizeof d);
	update (1 , inf , 1 , n , 1);
	for (int r = 0;r < p;r ++)
	{
		for (int i : a[r])
			update (i , r , 1 , n , 1);
		while (l <= d[1]) R[l ++] = s[r];
	}
	s[p] = inf;
	lg[0] = -1;
	for (int i = 0;i <= p;i ++) f[i + 1][0] = s[i] - R[i] , lg[i + 1] = lg[i + 1 >> 1] + 1;
	for (int k = 1;k <= lg[p + 1];k ++)
		for (int i = 1;i + (1 << k) - 1 <= p + 1;i ++)
			f[i][k] = max (f[i][k - 1] , f[i + (1 << k - 1)][k - 1]);
	cin >> q;
	while (q --)
	{
		int x , y , c;
		cin >> x >> y >> c;
		if (y + c < s[0] || x - c > s[p - 1])
			cout << "No\n";
		else
			cout << (y - x + c + getmax (x - c , x) >= 0 ? "Yes\n" : "No\n");
	}
	return 0;
}
2025/2/5 21:00
加载中...