Page Contents
C. Building a Fence SOLUTION CodeForces
Educational Codeforces Round 101 (Rated for Div. 2)
- The first line contains a single integer t (1≤t≤104) — the number of test cases.
- The first line of each test case contains two integers n and k (2≤n≤2⋅105; 2≤k≤108) — the number of sections in the fence and the height of each section.
- The second line of each test case contains n integers h1,h2,…,hn (0≤hi≤108), where hi is the ground level beneath the i-th section.
- It’s guaranteed that the sum of n over test cases doesn’t exceed 2⋅105.
- For each test case print YES if it’s possible to build the fence that meets all rules. Otherwise, print NO.
- You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).
- In the first test case, one of the possible fences is shown in the picture.
- In the second test case, according to the second rule, you should build both sections on the corresponding ground levels, and since k=3, h1=0, and h2=2 the first rule is also fulfilled.
- In the third test case, according to the second rule, you should build the first section on height 3 and the third section on height 2. According to the first rule, the second section should be on the height of at least 2 (to have a common side with the first section), but according to the third rule, the second section can be built on the height of at most h2+k−1=1.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <utility>
#define INF 999999999
using namespace std;
typedef long long ll;
int t;
int n,k,h[200005];
int can[2][200005];
void init()
{
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>h[i];
can[0][1]=h[1];
can[1][1]=h[1]+k;
}
void solve()
{
for(int i=2;i<n;i++)
{
int minh,maxh;
minh=h[i];
maxh=h[i]+k-1+k;
if(minh < can[1][i-1] && maxh > can[0][i-1])
{
can[0][i]=max(minh,can[0][i-1]-k+1);
can[1][i]=min(maxh,can[1][i-1]+k-1);
}
else
{
cout<<“NO”<<endl;
return;
}
}
if(h[n] < can[1][n-1] && h[n]+k > can[0][n-1] )
{
cout<<“YES”<<endl;
}
else
{
cout<<“NO”<<endl;
}
}
int main()
{
cin>>t;
while(t–)
{
init();
solve();
}
}
RELATED :
A. Regular Bracket Sequence SOLUTION CodeForces
B. Red and Blue SOLUTION CodeForces
C. Building a Fence SOLUTION CodeForces
D. Ceil Divisions SOLUTION CodeForces