AtCoder Grand Contest 072 E - Alice in linear land

程序员文章站 2022-04-13 20:42:23

...

Time limit : 2sec / Memory limit : 256MB

Score : 900 points

Problem Statement

Alice lives on a line. Today, she will travel to some place in a mysterious vehicle. Initially, the distance between Alice and her destination is D. When she input a number x to the vehicle, it will travel in the direction of the destination by a distance of x if this move would shorten the distance between the vehicle and the destination, and it will stay at its position otherwise. Note that the vehicle may go past the destination when the distance between the vehicle and the destination is less than x.

Alice made a list of N numbers. The i-th number in this list is di. She will insert these numbers to the vehicle one by one.

However, a mischievous witch appeared. She is thinking of rewriting one number in the list so that Alice will not reach the destination after N moves.

She has Q plans to do this, as follows:

Rewrite only the qi-th number in the list with some integer so that Alice will not reach the destination.
Write a program to determine whether each plan is feasible.

Constraints

1≤N≤5*105
1≤Q≤5*105
1≤D≤109
1≤di≤109(1≤i≤N)
1≤qi≤N(1≤i≤Q)
D and each di are integers.

Input

Input is given from Standard Input in the following format:

N D
d1 d2 … dN
Q
q1 q2 … qQ

Output

Print Q lines. The i-th line should contain YES if the i-th plan is feasible, and NO otherwise.

Sample Input 1

4 10
3 4 3 3
2
4 3

Sample Output 1

NO
YES
For the first plan, Alice will already arrive at the destination by the first three moves, and therefore the answer is NO. For the second plan, rewriting the third number in the list with 5 will prevent Alice from reaching the destination as shown in the following figure, and thus the answer is YES.
AtCoder Grand Contest 072 E - Alice in linear land

Sample Input 2

5 9
4 4 2 3 2
5
1 4 2 3 5

Sample Output 2

YES
YES
YES
YES
YES
Alice will not reach the destination as it is, and therefore all the plans are feasible.

Sample Input 3

6 15
4 3 5 4 2 1
6
1 2 3 4 5 6

Sample Output 3

NO
NO
YES
NO
NO
YES

Gist

一个人开着车，想到达距离为 D 的目的地，并依次有 N 条指令（d1—dn）。
她每进行一次操作（输入指令 x），如果 x∗2<D 就会往前走 x 过了就调转车头。
又有 Q 个询问，每个询问一个 qi ，问是否能修改第 qi 条指令使她不能到达目的地。
数据范围：1≤N,Q≤5∗105，1≤D,di≤109

Solution

设某一时刻距离为 x ，接下来的指令是 d 。
可得下一位置的距离为 x′=min(x,|x−d|) 。
再设 f[i] 表示满足从 x 出发执行指令 di—dn 后不能到达目的地的 最小的x 。
若求出 f[i] ，就能求出答案了！——对于询问 qi=i ，若：
从 D 出发执行指令 d1—di−1 到达的位置 ≥f[i+1] ，则是 YES ，否则是 NO 。
那么边界显然有：f[n+1]=1
考虑从后往前逆推出 f[i] 。
若 di≥f[i+1]∗2 ，则执行后位置不变，则有 f[i]=f[i+1] 。
若 di<f[i+1]∗2 ，则可以执行，必须往后推 di 格，则有 f[i]=f[i+1]+di 。
这样就求出 f[i] 了，总时间复杂度为 O(N) 。

Code

#include<cstdio>
#include<cctype>
using namespace std;
const int N=5e5+5;
int a[N],d[N],f[N];
inline int read()
{
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) w|=ch=='-',ch=getchar();
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
inline int min(int x,int y)
{
    return x<y?x:y;
}
inline int abs(int x)
{
    return x<0?-x:x;
}
int main()
{
    int n=read();
    a[0]=read();
    for(int i=1;i<=n;i++)
    {
        d[i]=read();
        a[i]=min(a[i-1],abs(a[i-1]-d[i]));
    }
    f[n+1]=1;
    for(int i=n;i;i--)
    {
        f[i]=f[i+1];
        if(d[i]<f[i]<<1) f[i]+=d[i];
    }
    int q=read();
    while(q--)
    {
        int x=read();
        puts(a[x-1]>=f[x+1]?"YES":"NO");
    }
    return 0;
}