abc f WA1 求调
  • 板块学术版
  • 楼主wild_asriel_X
  • 当前回复0
  • 已保存回复0
  • 发布时间2025/1/11 21:46
  • 上次更新2025/1/12 11:17:57
查看原帖
abc f WA1 求调
1351568
wild_asriel_X楼主2025/1/11 21:46
#include<bits/stdc++.h>
#define int long long
#define pii pair<long long,long long>
#define mp make_pair
#define pb push_back
using namespace std;
long long n,m,a,b,l[20004],r[20004],qwq=0;
map<long long,bool>u;
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>a>>b;
	for(long long i=a; i<=b; i++) {
		qwq=__gcd(qwq,i);
	}
	long long la=1;
	u[1]=1;
	for(int i=1; i<=m; i++) {
		cin>>l[i]>>r[i];
	}
	r[0]=0;
	l[m+1]=n+1;
	r[m+1]=n+1;
	for(int j=1; j<=b; j++) {
		for(int k=a; k<=b; k++) {
			u[j]|=u[j-k];
		}
	}
	for(int i=0; i<=m; i++) {
		if(l[i+1]-r[i]<=400) {
			long long cnt=0;
			for(int j=r[i]; j<=r[i]+b-a; j++) {
				cnt+=u[j];
			}
			for(int j=r[i]+b+1; j<l[i+1]; j++) {
				cnt-=u[j-b-1];
				cnt+=u[j-a];
				u[j]=(cnt!=0);
			}
		} else {
			bool hv=0;
			for(int j=r[i]+1; j<=r[i]+b; j++) {
				if(u[j])hv=1;
			}
			for(int j=l[i+1]-b; j<l[i+1]; j++) {
				if((j-1)%qwq==0)u[j]=hv;
			}
		}
		if(r[i+1]-l[i+1]>=b) {
			cout<<"No";
			return 0;
		} else {
			for(int j=l[i+1]; j<=r[i+1]; j++) {
				u[j]=0;
			}
			for(int j=r[i+1]+1; j<=r[i+1]+b; j++) {
				for(int k=a; k<=b; k++) {
					u[j]|=u[j-k];
				}
			}
		}
	}
	if(u[n]) {
		cout<<"Yes";
	} else {
		cout<<"No";
	}
	return 0;
}
2025/1/11 21:46
加载中...