Submission #2067977

---

Source Code Expand

#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,NAME,...) NAME
#define pr(...) GET_MACRO(__VA_ARGS__,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__)
#define pr1(a) (#a)<<"="<<(a)
#define pr2(a,b) pr1(a)<<", "<<pr1(b)
#define pr3(a,b,c) pr2(a,b)<<", "<<pr1(c)
#define pr4(a,b,c,d) pr3(a,b,c)<<", "<<pr1(d)
#define pr5(a,b,c,d,e) pr4(a,b,c,d)<<", "<<pr1(e)
#define int long long
#define double long double
using namespace std;
const int N = 100010;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
typedef pair<int,int> P;
typedef long long ll;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
ostream& operator<<(ostream& o,P p){return o<<"("<<p.first<<","<<p.second<<")";}
istream& operator>>(istream& i,P &p){return i>>p.first>>p.second;}
ostream& operator<<(ostream& o,vector<auto> &a){int i=0;for(auto t:a)o<<(i++?" ":"")<<t;return o;}
istream& operator>>(istream& i,vector<auto> &a){for(auto &t:a)i>>t;return i;}
void prArr(auto a,string s=" "){int i=0;for(auto t:a)cout<<(i++?s:"")<<t;cout<<endl;}


signed main(){
  int n,L;
  cin>>n>>L;
  vector<int> X(n);
  cin>>X;

  L *= 100;
  for(int i=0;i<n;i++) X[i] *= 100;
  
  vector<P> bar;
  for(int i=0;i<n;i++){
    int l = X[i], r = X[i];
    while(i + 1 < n && X[i+1] - X[i] <= L) r = X[++i];
    bar.push_back(P(l,r));
  }

  bar.push_back(P(INF,INF));

  int ans = 1;

  for(auto b:bar) if(b.second-b.first+1+1 >= L) ans = 0;
  if(ans == 0) {cout<<"NO"<<endl;return 0;}

  auto must = [&](int pos){
    auto b = *lower_bound(bar.begin(),bar.end(),P(pos,0));
    int l = b.first, r = b.second;
    if(pos < l && r < pos+L) return 1;
    return 0;
  };

  auto canJump=[&](int pos){
    auto b = *lower_bound(bar.begin(),bar.end(),P(pos,0));
    int l = b.first, r = b.second;
    if(l<=pos + L + 1) return 0;
    return 1;
  };

  auto move =[&](int pos){
    auto b = *lower_bound(bar.begin(),bar.end(),P(pos,0));
    int l = b.first, r = b.second;
    return r + 1 - L;
  };

  int pos = 0;
  while(ans){
    if(pos > bar[bar.size()-2].second) break;
    if(must(pos)) ans &= canJump(pos+L),pos = pos+L+L;
    else pos = move(pos);
  }
  
  cout<<(ans? "YES":"NO")<<endl;
  
  return 0;
}

Submission Info

Judge Result