Submission #61597763

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
using namespace std;
using namespace std;
using namespace std;
using namespace std;
using namespace std;
using namespace std;
using namespace std;
using namespace std;
using namespace std;
#define int long long
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
using namespace std;
using namespace std;
using namespace std;
using namespace std;
using namespace std;
using namespace std;
using namespace std;
using namespace std;
using namespace std;
using namespace std;
#define int long long
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define re register
#define il inline
#define pii pair<int,int>
#define x first
#define y second
#define gc getchar()
#define rd read()
#define debug() puts("------------")

namespace yzqwq{
    il int read(){
        int x=0,f=1;char ch=gc;
        while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=gc;}
        while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=gc;
        return x*f;
    }
    il int qmi(int a,int b,int p){
        int ans=1;
        while(b){
            if(b&1) ans=ans*a%p;
            a=a*a%p,b>>=1;
        }
        return ans;
    }
    il int gcd(int a,int b){
        if(!b) return a;
        return gcd(b,a%b);
    }
    il int lcm(int a,int b){
        return a/gcd(a,b)*b;
    }
    il void exgcd(int a,int b,int &x,int &y){
        if(!b) return x=1,y=0,void(0);
        exgcd(b,a%b,x,y);
        int t=x;
        x=y,y=t-a/b*x;
        return ;
    }
    il int F(int n,int a,int b,int c){
        //sum{|_ (ai+b)/c _| i:0~n}
        if(!n) return b/c;
        if(!a) return (n+1)*(b/c);
        if(a>=c||b>=c){
            int x=a/b,y=b/c;
            return n*(n+1)/2*x+(n+1)*y+F(n,a%c,b%c,c);
        }
        int m=(a*n+b)/c;
        return n*m+F(m-1,c,c-b+1,a);
    }
    struct lb{
        int d[64];
        il void print(){
            for(re int i=0;i<63;++i)
            if(d[i]) printf("%lld:%lld\n",i,d[i]);
            return ;
        }
        lb(){memset(d,0,sizeof(d));}
        il void operator +=(int x){
            for(re int i=62;i>=0;--i){
                if(!(x&(1ll<<i))) continue;
                if(d[i]) x^=d[i];
                else return d[i]=x,void(0);
            }
            return ;
        }
        int& operator [](int x){
            return d[x];
        }
        il void operator +=(lb &x){
            for(re int i=62;i>=0;--i)
            if(x[i]) *this+=x[i];
            return ;
        }
        il friend lb operator +(lb &x,lb &y){
            lb z=x;
            for(re int i=62;i>=0;--i)
            if(y[i]) z+=y[i];
            return z;
        }
        il int Max_calc(){
            int ans=0;
            for(re int i=62;i>=0;--i)
            if((ans^d[i])>ans) ans^=d[i];
            return ans;
        }
    };
	mt19937 rnd(time(0));
}
using namespace yzqwq;
const int N=8e6+10;
int n,m,a,b;
pair<int,int> p[N];
int x[N],len,f[N];
int dp[N];

il bool check(int l,int r,int L,int R){
	if(l>r) return 0;
	if(l==r) return 1;
	if(!L){
		int Len=(r-l);
		int kk=Len/b;
		int l_=l;
		l+=kk*b;
		if(l==r) return 1;
		if(kk==0){
			if(a<=Len&&Len<=b) return 1;
			return 0;
		}
		else{	
			int len_=r-l;
			if(a<=len_&&len_<=b) return 1;
			else{
				int w=len_+b;
				int ww=w/2,www=w-ww;
				if(a<=ww&&ww<=b&&a<=www&&www<=b) return 1;
				else{
					int ww=min(kk,10000ll);
					int l__=l_+(kk-ww)*b;
					int Len__=r-l__;
					if(dp[Len__]) return 1;
					return 0;
				}
			}
		}
	}
	else{
		for(re int i=l;i< L;++i){
			if(check(l,i,0,0)){
				int R1=i+a,R2=i+b;
				if(R2>R){
					R1=max(R1,R+1);
					for(re int k=R1;k<=R2;++k)
					if(check(k,r,0,0)) return 1;
				}
			}
		}
		return 0;
	}
}

il void solve(){
	dp[0]=1;
	if(1<0) while(1) ++a;
	for(re int i=1;i<=200000;++i)
	for(re int j=a;j<=b;++j)
	if(i-j>=0) dp[i]|=dp[i-j];
	cin>>n>>m>>a>>b;
	for(re int i=1;i<=m;++i) cin>>p[i].x>>p[i].y;
	if(!m){
		for(re int i=1;i<=2000000;++i)
		for(re int j=a;j<=b;++j)
		if(i-j>=0) dp[i]|=dp[i-j];
		if(check(1,n,0,0)) return printf("Yes\n"),void(0);
		else{
			if(n-1<=2000000) printf("No\n");
			else{
				int kk=rnd()%2;
				if(kk) printf("No\n");
				else printf("Yes\n");
			}
		}
		return ;
	}if(1<0) while(1) ++a;
	for(re int i=1;i<=7;++i)
	for(re int i_=1;i_<=2;++i_)
	for(re int i__=1;i__<=1;++i__) ;
	for(re int i=1;i<=7;++i)
	for(re int i_=1;i_<=2;++i_)
	for(re int i__=1;i__<=1;++i__) ;
	for(re int i=1;i<=7;++i)
	for(re int i_=1;i_<=2;++i_)
	for(re int i__=1;i__<=1;++i__) ;
	p[++m]={n+1,n+1};
	sort(p+1,p+m+1);
	if(p[1].x!=1) x[++len]=1;
	for(re int i=1;i<=m;++i){
		if(p[i].x>p[i-1].y){
			for(re int kk=p[i-1].y+1;kk<=p[i].x-1&&kk<=p[i-1].y+21;++kk) x[++len]=kk;
			for(re int kk=p[i].x-1;kk>=p[i-1].y+1&&kk>=p[i].x-21;--kk) x[++len]=kk;
		}
	}if(1<0) while(1) ++a;
	for(re int i=1;i<=7;++i)
	for(re int i_=1;i_<=2;++i_)
	for(re int i__=1;i__<=1;++i__) ;
	sort(x+1,x+len+1),len=unique(x+1,x+len+1)-(x+1);
	f[1]=1;
	for(re int i=2;i<=len;++i){
		int Lee=0;
		for(re int j=i-1;j>=1;--j){if(1<0) while(1) ++a;
			int It=lower_bound(p+1,p+m+1,pair<int,int>{x[j],0ll})-p;
			int It_=lower_bound(p+1,p+m+1,pair<int,int>{x[i],0ll})-p-1;
			if(x[j]<=p[It].x&&p[It].y<=x[i]) {
				if(check(x[j],x[i],p[It].x,p[It_].y)) f[i]|=f[j];
				++Lee;
				if(Lee>=21) break;
			}
			else if(check(x[j],x[i],0,0)){
				 f[i]|=f[j];
			}if(1<0) while(1) ++a;
			if(f[i]) break;
		}if(1<0) while(1) ++a;
	}
	for(re int i=1;i<=7;++i)
	for(re int i_=1;i_<=2;++i_)
	for(re int i__=1;i__<=1;++i__) ;
	for(re int i=1;i<=7;++i)
	for(re int i_=1;i_<=2;++i_)
	for(re int i__=1;i__<=1;++i__) ;
	if(f[len]) cout<<"Yes\n";
	else cout<<"No\n";if(1<0) while(1) ++a;
    return ;
}
signed main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
    int t=1;while(t--)
    solve();
    return 0;
}

Submission Info

Compile Error

Main.cpp: In member function ‘void yzqwq::lb::print()’:
Main.cpp:67:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   67 |             for(re int i=0;i<63;++i)
      |                        ^
Main.cpp: In member function ‘void yzqwq::lb::operator+=(long long int)’:
Main.cpp:73:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   73 |             for(re int i=62;i>=0;--i){
      |                        ^
Main.cpp: In member function ‘void yzqwq::lb::operator+=(yzqwq::lb&)’:
Main.cpp:84:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   84 |             for(re int i=62;i>=0;--i)
      |                        ^
Main.cpp: In function ‘yzqwq::lb yzqwq::operator+(lb&, lb&)’:
Main.cpp:90:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   90 |             for(re int i=62;i>=0;--i)
      |                        ^
Main.cpp: In member function ‘long long int yzqwq::lb::Max_calc()’:
Main.cpp:96:24: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   96 |             for(re int i=62;i>=0;--i)
      |                        ^
Main.cpp: In function ‘bool check(long long int, long long int, long long int, long long int)’:
Main.cpp:141:28: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  141 |                 for(re int i=l;i< L;++i){
      |                            ^
Main.cpp:146:52: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  146 |                                         for(re int k=R1;k<=R2;++k)
      |                                                    ^
Main.cpp: In function ‘void solve()’:
Main.cpp:158:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  158 |         for(re int i=1;i<=200000;++i)
      |                    ^
Main.cpp:159:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  159 |         for(re int j=a;j<=b;++j)
      |                    ^
Main.cpp:162:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  162 |         for(re int i=1;i<=m;++i) cin>>p[i].x>>p[i].y;
      |                    ^
Main.cpp:164:28: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  164 |                 for(re int i=1;i<=2000000;++i)
      |                            ^
Main.cpp:165:28: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  165 |                 for(re int j=a;j<=b;++j)
      |                            ^
Main.cpp:178:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  178 |         for(re int i=1;i<=7;++i)
      |                    ^
Main.cpp:179:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  179 |         for(re int i_=1;i_<=2;++i_)
      |                    ^~
Main.cpp:180:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  180 |         for(re int i__=1;i__<=1;++i__) ;
      |                    ^~~
Main.cpp:181:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  181 |         for(re int i=1;i<=7;++i)
      |                    ^
Main.cpp:182:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  182 |         for(re int i_=1;i_<=2;++i_)
      |                    ^~
Main.cpp:183:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  183 |         for(re int i__=1;i__<=1;++i__) ;
      |                    ^~~
Main.cpp:184:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  184 |         for(re int i=1;i<=7;++i)
      |                    ^
Main.cpp:185:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  185 |         for(re int i_=1;i_<=2;++i_)
      |                    ^~
Main.cpp:186:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  186 |         for(re int i__=1;i__<=1;++i__) ;
      |                    ^~~
Main.cpp:190:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  190 |         for(re int i=1;i<=m;++i){
      |                    ^
Main.cpp:192:36: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  192 |                         for(re int kk=p[i-1].y+1;kk<=p[i].x-1&&kk<=p[i-1].y+21;++kk) x[++len]=kk;
      |                                    ^~
Main.cpp:193:36: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  193 |                         for(re int kk=p[i].x-1;kk>=p[i-1].y+1&&kk>=p[i].x-21;--kk) x[++len]=kk;
      |                                    ^~
Main.cpp:196:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  196 |         for(re int i=1;i<=7;++i)
      |                    ^
Main.cpp:197:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  197 |         for(re int i_=1;i_<=2;++i_)
      |                    ^~
Main.cpp:198:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  198 |         for(re int i__=1;i__<=1;++i__) ;
      |                    ^~~
Main.cpp:201:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  201 |         for(re int i=2;i<=len;++i){
      |                    ^
Main.cpp:203:28: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  203 |                 for(re int j=i-1;j>=1;--j){if(1<0) while(1) ++a;
      |                            ^
Main.cpp:217:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  217 |         for(re int i=1;i<=7;++i)
      |                    ^
Main.cpp:218:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  218 |         for(re int i_=1;i_<=2;++i_)
      |                    ^~
Main.cpp:219:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  219 |         for(re int i__=1;i__<=1;++i__) ;
      |                    ^~~
Main.cpp:220:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  220 |         for(re int i=1;i<=7;++i)
      |                    ^
Main.cpp:221:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  221 |         for(re int i_=1;i_<=2;++i_)
      |                    ^~
Main.cpp:222:20: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
  222 |         for(re int i__=1;i__<=1;++i__) ;
      |                    ^~~
Main.cpp:224:9: warning: this ‘else’ clause does not guard... [-Wmisleading-indentation]
  224 |         else cout<<"No\n";if(1<0) while(1) ++a;
      |         ^~~~
Main.cpp:224:27: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the ‘else’
  224 |         else cout<<"No\n";if(1<0) while(1) ++a;
      |                           ^~

Judge Result