为什么 WA 且只 WA 第 47 个点/yiw
查看原帖
为什么 WA 且只 WA 第 47 个点/yiw
482610
Mortidesperatslav楼主2025/1/17 13:34
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, a[500005], b[500005], pd[1000005], x, y;
int S[9000005], top;
unordered_map<int, int> f, forbid;
bool check(int u, int v){
	if (forbid[v])
		return 0;
	if (v - u > 1000000)
		return 1;
	else
		return pd[v - u];
}
void erase(int x){
	forbid[x] = 1;
}
void insert(int x){
//	if (forbid[x])
//		return;
	S[++top] = x;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> m >> x >> y;
	for (int i = 1; i <= m; i++){
		cin >> a[i] >> b[i];
		if (b[i] - a[i] + 1 >= y){
			cout << "No";
			return 0;
		}
	}
	if (x == y){
		if ((n - 1) % x != 0){
			cout << "No";
			return 0;
		}
		for (int i = 1; i <= m; i++){
			for (int j = a[i]; j <= b[i]; j++){
				if ((j - 1) % x == 0){
					cout << "No";
					return 0;
				}
			}
		}
		cout << "Yes";
		return 0;
	}
	pd[0] = 1;
	for (int i = 0; i <= 1000000; i++){
		if (!pd[i])
			continue;
		for (int j = x; j <= y; j++)
			pd[i + j] = 1;
	}
	for (int i = 1; i <= m; i++){
		for (int j = a[i]; j <= b[i]; j++){
			erase(j);
			insert(j);
		}
	}
	insert(1);
	insert(n);
	for (int i = 1; i <= m; i++){
		for (int j = a[i] - 20; j < a[i]; j++)
			insert(j);
		for (int j = b[i] + 1; j <= b[i] + 20; j++)
			insert(j);
	}
	sort(S + 1, S + 1 + top);
	top = unique(S + 1, S + 1 + top) - S - 1;
	f[1] = 1;
	for (int i = 1; i <= top; i++){
		if (f[S[i]] == 0)
			continue;
		bool flg = 0;
		for (int j = i + 1; j <= min(top, i + 20); j++){
			if (forbid[S[j]])
				flg = 1;
			if (flg && S[j] - S[i] > y)
				break;
			if (check(S[i], S[j]))
				f[S[j]] = 1;
		}
	}
	if (f[n])
		cout << "Yes";
	else
		cout << "No";
	return 0;
}
2025/1/17 13:34
加载中...