F - Dangerous Sugoroku
Source: atcoder
Difficulty: 550

Problem Statement
There are
N
squares arranged in a row, labeled
1, 2, \ldots, N
from left to right.
You are given
M
pairs of integers
(L_1, R_1), \ldots, (L_M, R_M)
.
A square
j
is defined to be
bad
if and only if there exists some
i
such that
L_i \leq j \leq R_i
.
Determine whether you can move from square
1
to square
N
by repeatedly performing the following action:
Let your current square be
x
. Choose an integer
i
that satisfies all of the following conditions, and move to square
x + i
.
A \leq i \leq B
x + i \leq N
Square
x + i
is not bad.
Constraints
2 \leq N \leq 10^{12}
0 \leq M \leq 2 \times 10^4
1 \leq A \leq B \leq 20
1 < L_i \leq R_i < N \ (1 \leq i \leq M)
R_i < L_{i+1} \ (1 \leq i \leq M - 1)
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
M
A
B
L_1
R_1
L_2
R_2
\vdots
L_M
R_M
Output
If it is possible to reach square
N
by repeating the action described in the problem statement, print
Yes
. Otherwise, print
No
.
Sample Input 1
24 2 3 5
7 8
17 20
Sample Output 1
Yes
You can move to square
N
in this way:
1 \to 6 \to 9 \to 12 \to 16 \to 21 \to 24
.
Sample Input 2
30 1 5 8
4 24
Sample Output 2
No
Sample Input 3
100 4 10 11
16 18
39 42
50 55
93 99
Sample Output 3
Yes

C++ solution:
#include <bits/stdc++.h>

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;

using ll=long long;
using LL=__int128;
using ld=long double;
using uint=unsigned int;
using ull=unsigned long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
template<typename T> using vc=vector<T>;
template<typename T> using vvc=vector<vc<T>>;
template<typename T> using vvvc=vector<vvc<T>>;
using vi=vc<int>;
using vvi=vvc<int>;
using vd=vc<ld>;
using vvd=vvc<ld>;
using vl=vc<ll>;
using vvl=vvc<ll>;
using vs=vc<string>;
using vp=vc<pll>;
using vvp=vvc<pll>;

#define overload3(_1,_2,_3,name,...) name
#define rep1(n) for(ll _=0;_<ll(n);_++)
#define rep2(i,n) for(ll i=0;i<ll(n);i++)
#define rep3(i,a,b) for(ll i=ll(a);i<ll(b);i++)
#define rep(...) overload3(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(n) for(ll _=ll(n);_--;)
#define rrep2(i,n) for(ll i=ll(n);i--;)
#define rrep3(i,a,b) for(ll i=ll(b);i-->ll(a);)
#define rrep(...) overload3(__VA_ARGS__,rrep3,rrep2,rrep1)(__VA_ARGS__)

#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()

istream& operator>>(istream& is,__int128& v){
    string s;
    is>>s;
    v=0;
	rep(i,s.size())if(isdigit(s[i])) v=v*10+s[i]-'0';
	if(s[0]=='-') v*=-1;
    return is;
}
ostream& operator<<(ostream& os,__int128 v){
	ostream::sentry s(os);
	if(s){
		__uint128_t t=v<0?-v:v;
		char buf[128];
		char* d=end(buf);
		do{
			d--;
			*d="0123456789"[t%10];
			t/=10;
		}while(t);
		if(v<0){
			d--;
			*d='-';
		}
		int len=end(buf)-d;
		if(os.rdbuf()->sputn(d,len)!=len) os.setstate(ios_base::badbit);
	}
	return os;
}
template<typename S,typename T>
ostream& operator<<(ostream& os,pair<S,T> a){
	os<<a.first<<' '<<a.second;
	return os;
}
template<typename T>
ostream& operator<<(ostream& os,vector<T> a){
	if(a.empty()) return os;
	os<<a[0];
	rep(i,1,a.size()) os<<' '<<a[i];
	return os;
}
template<typename T>
ostream& operator<<(ostream& os,vector<vector<T>> a){
	if(a.empty()) return os;
	os<<a[0];
	rep(i,1,a.size()) os<<endl<<a[i];
	return os;
}
void output(auto x){cout<<x<<endl;}
template<typename T>
void output(vector<T> a,bool next_line=0){
	if(next_line){
		for(auto x:a) output(x);
	}
	else cout<<a<<endl;
}

void debug(auto ...vs){
	((cout<<vs<<", "),...)<<endl;
}

void syosu(int x=15){cout<<fixed<<setprecision(x);}
void YN(bool x){cout<<(x?"Yes":"No")<<endl;}
void chmin(auto &x,auto y){if(x>y) x=y;}
void chmax(auto &x,auto y){if(x<y) x=y;}

template<typename T>
void read(vector<T> &a,int n,int off=0){
	a=vector<T>(n);
	for(auto &i:a){
		cin>>i;
		i-=off;
	}
}

void read(vs &a,int n){
	a=vs(n);
	for(auto &i:a) cin>>i;
}

template<typename T>
void read(vector<pair<T,T>> &a,int n,int off=0){
	a=vector<pair<T,T>>(n);
	for(auto &[x,y]:a){
		cin>>x>>y;
		x-=off,y-=off;
	}
}

template<typename T>
void read(vector<vector<T>> &a,int n,int m,int off=0){
	a=vector<vector<T>>(n,vector<T>(m));
	for(auto &i:a) for(auto &j:i){
		cin>>j;
		j-=off;
	}
}

template<typename T>
void readGraph(vector<vector<T>> &g,int n,int m,bool rv=1,int off=1){
	g=vector<vector<T>>(n);
	for(int i=0;i<m;i++){
		T u,v;
		cin>>u>>v;
		u-=off,v-=off;
		g[u].emplace_back(v);
		if(rv) g[v].emplace_back(u);
	}
}

template<typename T>
void readGraph(vector<vector<pair<T,T>>> &g,int n,int m,bool id=0,bool rv=1,int off=1){
	g=vector<vector<pair<T,T>>>(n);
	for(int i=0;i<m;i++){
		if(id){
			T u,v;
			cin>>u>>v;
			u-=off,v-=off;
			g[u].emplace_back(v,i);
			if(rv) g[v].emplace_back(u,i);
		}
		else{
			T u,v,w;
			cin>>u>>v>>w;
			u-=off,v-=off;
			g[u].emplace_back(v,w);
			if(rv) g[v].emplace_back(u,w);
		}
	}
}

string toBinary(ll x,ll n,bool rev=0){
	assert(0<=x&&x<1LL<<n);
	string s(n,'0');
	for(int i=0;i<n;i++) if(x&1LL<<i) s[n-i-1]='1';
	if(rev) reverse(s.begin(),s.end());
	return s;
}

constexpr ll inf=1<<30;
constexpr ll INF=1ll<<60;
const ld pi=acosl(-1);
constexpr ld eps=1e-9;
//constexpr ll mod=1e9+7;
constexpr ll mod=998244353;
constexpr int dx[9]={-1,0,1,0,1,1,-1,-1,0};
constexpr int dy[9]={0,1,0,-1,1,-1,1,-1,0};

void main2();

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	ll q=1;
//	cin>>q;
	while(q--) main2();
}

void main2(){
	ll n,m,A,B;
	cin>>n>>m>>A>>B;
	vp a;
	read(a,m,1);
	if(A==B){
		bool flag=(n-1)%A==0;
		for(auto [l,r]:a) flag&=(r/A-(l-1)/A==0);
		YN(flag);
		return;
	}
	unsigned int S=1;
	const unsigned int T=(1<<B+1)-(1<<A);
	const unsigned int U=(1<<23)-1;
	ll I=0;
	for(ll x=1;x<n;x++){
		S<<=1;
		if(S==0) break;
		if(I<m&&a[I].second<x) I++;
		if(I<m&&a[I].first<=x&&x<=a[I].second) continue;
		if(S&T) S|=1;
		if((S&U)==U){
			if(I==m){
				S=1;
				break;
			}
			x=a[I].first-1;
		}
	}
	YN(S&1);
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var wr = bufio.NewWriter(os.Stdout)

func out(x ...interface{}) {
	fmt.Fprintln(wr, x...)
}

func outSlice[T any](s []T) {
	for i := 0; i < len(s)-1; i++ {
		fmt.Fprint(wr, s[i], " ")
	}
	fmt.Fprintln(wr, s[len(s)-1])
}

func getI() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func getF() float64 {
	sc.Scan()
	i, e := strconv.ParseFloat(sc.Text(), 64)
	if e != nil {
		panic(e)
	}
	return i
}

func getInts(N int) []int {
	ret := make([]int, N)
	for i := 0; i < N; i++ {
		ret[i] = getI()
	}
	return ret
}

func getS() string {
	sc.Scan()
	return sc.Text()
}

// min, max, asub, absなど基本関数
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// min for n entry
func nmin(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = min(ret, e)
	}
	return ret
}

// max for n entry
func nmax(a ...int) int {
	ret := a[0]
	for _, e := range a {
		ret = max(ret, e)
	}
	return ret
}

func chmin(a *int, b int) bool {
	if *a < b {
		return false
	}
	*a = b
	return true
}

func chmax(a *int, b int) bool {
	if *a > b {
		return false
	}
	*a = b
	return true
}

func asub(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func abs(a int) int {
	if a >= 0 {
		return a
	}
	return -a
}

func lowerBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] >= x
	})
	return idx
}

func upperBound(a []int, x int) int {
	idx := sort.Search(len(a), func(i int) bool {
		return a[i] > x
	})
	return idx
}

func solve() bool {
	n, m, a, b := getI(), getI(), getI(), getI()
	l := make([]int, m)
	r := make([]int, m)
	for i := 0; i < m; i++ {
		l[i], r[i] = getI()-1, getI()
	}

	if a == b {
		for i := 0; i < m; i++ {
			x := (r[i] - 1) / a * a
			if l[i] <= x {
				return false
			}
		}
		if (n-1)%a != 0 {
			return false
		}
		return true
	}

	dp := make([]int, b)
	dp[0] = 1
	i := 0
	l = append(l, n)
	r = append(r, n)
	m++
	for j := 0; j < m; j++ {
		w := l[j] - i - 1
		if w > a*a {
			allZero := true
			for _, v := range dp {
				if v != 0 {
					allZero = false
					break
				}
			}
			if allZero {
				return false
			}
			for k := 0; k < b; k++ {
				dp[k] = 1
			}
		} else {
			for k := 0; k < w; k++ {
				dp = append([]int{0}, dp...)
				for x := a; x <= b; x++ {
					dp[0] = dp[0] | dp[x]
				}
				dp = dp[:b]
			}
		}

		w = r[j] - l[j]
		if w >= b {
			return false
		}
		for k := 0; k < w; k++ {
			dp = append([]int{0}, dp[:b-1]...)
		}

		i = r[j] - 1
	}

	return dp[0] == 1
}

func main() {
	defer wr.Flush()
	sc.Split(bufio.ScanWords)
	sc.Buffer([]byte{}, math.MaxInt32)
	// this template is new version.
	// use getI(), getS(), getInts(), getF()

	if solve() {
		out("Yes")
	} else {
		out("No")
	}

}

Java solution:
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.NoSuchElementException;
import java.util.function.IntFunction;
import java.util.function.LongFunction;

public class Main {
	public static void main(String[] args) {
		Main o = new Main();
		o.solve();
	}

	public void solve() {
		FastScanner sc = new FastScanner(System.in);
		long N = sc.nextLong();
		int M = sc.nextInt();
		int A = sc.nextInt();
		int B = sc.nextInt();
		ArrayList<Range> range = new ArrayList<>();
		for (int i = 0; i < M; i++) {
			long L = sc.nextLong() - 1;
			long R = sc.nextLong() - 1;
			range.add(new Range(L, R, i));
		}

		for (int i = 0; i < M; i++) {
			Range r = range.get(i);
			if ( r.len() >= B ) {
				System.out.println(NO);
				return;
			}
		}

		if ( A == B ) {
			for (int i = 0; i < M; i++) {
				Range r = range.get(i);
				if ( r.L % A == 0 || r.R % A == 0 || r.L / A != r.R / A ) {
					System.out.println(NO);
					return;
				}
			}
			if ( (N - 1) % A == 0 ) {
				System.out.println(YES);
			} else {
				System.out.println(NO);
			}
			return;
		}

		range.add(new Range(N, N + B - 2, M));
		long p = 0;
		int b = 1;
		int MASK = ((1 << (B - A + 1)) - 1) << A;
		for (int i = 0; i <= M; i++) {
			if ( b == 0 ) {
				System.out.println(NO);
				return;
			}
			Range r = range.get(i);
			if ( r.L > p + B * B ) {
				p = r.L - B;
				b = (1 << B) - 1;
			}
			for (; p < r.L ;) {
				if ( (b & 1) == 1 ) {
					b |= MASK;
				}
				p += 1;
				b >>>= 1;
			}
			b &= ~((1 << r.len()) - 1);
		}
		if ( b != 0 ) {
			System.out.println(YES);
		} else {
			System.out.println(NO);
		}
	}

	class Range {
		long L = 0;
		long R = 0;
		int id = 0;
		Range(long L, long R, int i) {
			this.L = L;
			this.R = R;
			this.id = i;
		}
		int len() {
			return (int)(R - L + 1);
		}
	}

	static final char LF = '\n';
	static final char SPACE = ' ';
	static final String YES = "Yes";
	static final String NO = "No";
	void print(int[] array, char sep) {
		print(array, sep, n -> n, 0, array.length);
	}
	void print(int[] array, char sep, IntFunction<Integer> conv) {
		print(array, sep, conv, 0, array.length);
	}
	void print(int[] array, char sep, IntFunction<Integer> conv, int start, int end) {
		StringBuilder ans = new StringBuilder();
		for (int i = start; i < end; i++) {
			ans.append(conv.apply(array[i]));
			ans.append(sep);
		}
		ans.deleteCharAt(ans.length() - 1);
		System.out.println(ans.toString());
	}
	void print(long[] array, char sep) {
		print(array, sep, n -> n, 0, array.length);
	}
	void print(long[] array, char sep, LongFunction<Long> conv) {
		print(array, sep, conv, 0, array.length);
	}
	void print(long[] array, char sep, LongFunction<Long> conv, int start, int end) {
		StringBuilder ans = new StringBuilder();
		for (int i = start; i < end; i++) {
			ans.append(conv.apply(array[i]));
			ans.append(sep);
		}
		ans.deleteCharAt(ans.length() - 1);
		System.out.println(ans.toString());
	}
	void printYesNo(boolean yesno) {
		System.out.println(yesno ? YES : NO);
	}
	void printDouble(double val, int digit) {
		System.out.println(String.format("%." + digit + "f", val));
	}
	
	class FastScanner {
		private final InputStream in;
		private final byte[] buf = new byte[1024];
		private int ptr = 0;
		private int buflen = 0;
		FastScanner( InputStream source ) { this.in = source; }
		private boolean hasNextByte() {
			if ( ptr < buflen ) return true;
			else {
				ptr = 0;
				try { buflen = in.read(buf); } catch (IOException e) { e.printStackTrace(); }
				if ( buflen <= 0 ) return false;
			}
			return true;
		} 
		private int readByte() { if ( hasNextByte() ) return buf[ptr++]; else return -1; } 
		private boolean isPrintableChar( int c ) { return 33 <= c && c <= 126; }
		private boolean isNumeric( int c ) { return '0' <= c && c <= '9'; }
		private void skipToNextPrintableChar() { while ( hasNextByte() && !isPrintableChar(buf[ptr]) ) ptr++; }
		public boolean hasNext() { skipToNextPrintableChar(); return hasNextByte(); }
		public String next() {
			if ( !hasNext() ) throw new NoSuchElementException();
			StringBuilder ret = new StringBuilder();
			int b = readByte();
			while ( isPrintableChar(b) ) { ret.appendCodePoint(b); b = readByte(); }
			return ret.toString();
		}
		public long nextLong() {
			if ( !hasNext() ) throw new NoSuchElementException();
			long ret = 0;
			int b = readByte();
			boolean negative = false;
			if ( b == '-' ) { negative = true; if ( hasNextByte() ) b = readByte(); }
			if ( !isNumeric(b) ) throw new NumberFormatException();
			while ( true ) {
				if ( isNumeric(b) ) ret = ret * 10 + b - '0';
				else if ( b == -1 || !isPrintableChar(b) ) return negative ? -ret : ret;
				else throw new NumberFormatException();
				b = readByte();
			}
		}
		public int nextInt() { return (int)nextLong(); }
		public double nextDouble() { return Double.parseDouble(next()); }
	}
}

JavaScript solution:
"use strict";
var input=require("fs").readFileSync("/dev/stdin","utf8");
var cin=input.split(/ |\n/),cid=0;
function next(){return +cin[cid++];}
function nextstr(){return cin[cid++];}
function nextbig(){return BigInt(cin[cid++]);}
function nexts(n,a){return a?cin.slice(cid,cid+=n):cin.slice(cid,cid+=n).map(a=>+a);}
function nextssort(n,a){return a?cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>b-a):cin.slice(cid,cid+=n).map(a=>+a).sort((a,b)=>a-b);}
function nextm(h,w,a){var r=[],i=0;if(a)for(;i<h;i++)r.push(cin.slice(cid,cid+=w));else for(;i<h;i++)r.push(cin.slice(cid,cid+=w).map(a=>+a));return r;}
function xArray(v){var a=arguments,l=a.length,r="Array(a["+--l+"]).fill().map(x=>{return "+v+";})";while(--l)r="Array(a["+l+"]).fill().map(x=>"+r+")";return eval(r);}
var streams=[];function print(s){streams.push(s);}

var n,m,a,b,mp;

var myOut = main();
if(myOut !== undefined)console.log(String(myOut));
if(streams.length)console.log(streams.join("\n"));

function main(){
  var q = 1;
  while(q--)print(solve()?"Yes":"No");
}

function solve(){
  [n,m,a,b] = nexts(4);
  if(a === b){
    for(var i = 0; i < m; i++){
      var [l,r] = nexts(2); l--; r--;
      var t = Math.floor(l / a) * a;
      if(t === l || t+a <= r)return 0;
    }
    return (n-1) % a === 0;
  }
  mp = xArray(0,400);
  mp[0] = 1;
  for(var i = 0; i+a < 400; i++){
    if(!mp[i])continue;
    for(var j = a; j <= b; j++){
      if(i+j === 400)break;
      mp[i+j] = 1;
    }
  }
  var ok = [1];
  for(var i = 0; i < m; i++){
    var [l,r] = nexts(2);
    var mn = Math.max(r+1 - b, ok[0]);
    var t = [];
    for(var j = mn; j <= l-1; j++){
      if(f(ok,j))t.push(j);
    }
    if(t.length === 0)return 0;
    ok = t;
    ok.push(r);
    for(var j = r+1; j <= l-1+b; j++){
      if(f(ok,j)){
        ok.pop();
        ok.push(j);
        break;
      }
    }
  }
  return f(ok,n);
}

function f(ok,k){
  if(ok.at(-1)+380 <= k)return 1;
  for(var i = 0; i < ok.length; i++){
    if(ok[i] === k)return 1;
    for(var j = Math.max(a, ok.at(-1)-ok[i]); j <= b; j++){
      var v = ok[i] + j;
      if(v > k)break;
      if(mp[k-v])return 1;
    }
  }
  return 0;
}

Python solution:
import collections
def solve():
    N,M,A,B=map(int,input().split())
    L=[]
    R=[]
    for i in range(M):
        l,r=map(int,input().split())
        L.append(l-1)
        R.append(r)
        
    if A==B:
        for i in range(M):
            x=(R[i]-1)//A*A
            if L[i]<=x:
                return False
        
        if (N-1)%A:
            return False
        return True
    
    dp=1
    msk=(1<<B)-1
    to=(1<<(B+1))-(1<<A)
    L.append(N)
    R.append(N)
    M+=1
    i=0
    for j in range(M):
        w=L[j]-i-1
        if w>A*A:
            if dp==0:
                return False
            dp=msk
        else:
            for k in range(w):
                dp<<=1
                if dp&to:
                    dp|=1
                dp&=msk
                    
        w=R[j]-L[j]
        if w>=B:
            return False
        dp<<=w
        dp&=msk
            
        i=R[j]-1
    return dp&1

print("Yes" if solve() else "No")

Ruby solution:
(n,m,a,b),*e=$<.map{_1.split.map &:to_i}
x=2**b-t=c=1
e<<[n+1,n]
e.map{t=t*2&x|-2[t>>a-1]while 0<t&&t<x&&c<_1-1&&c+=1+a/b*(_1-2-c)/a*a
t=x&t>>_1+~c=_2}
$><<[:No,:Yes][t&1]