列表

详情

NC25721. Re: Trial of Devil

描述

    If you pass the previous trial of Devil Aguin, congratulations to you! But the real trial has just begun. This time, Devil Aguin provides you a sequence A consisting of n elements and a value k. Then he also offers you an operation to process the sequence.
    What you can do in one operation are as following:
    1. Select a k-length interval of A arbitrarily.

    2. Select a positive integer x arbitrarily.

    3. Turn element whose value is no more than x in the interval to 0.
    You can perform the operation as much as you like. It is clear that, when you perform the operation, the elements in A may be developed into 0 one by one. Now Devil Aguin gives you an order sequence C, which contains m elements ranging from 1 to n. He requires that for each , the -th element in A must turn to 0. And generally, for every i,j(i < j), the time -th element in A turning to 0 must be strictly earlier than -th element.
    Please judge if it is possible to meet the requirement.
    It is guaranteed that there is no same element in C.

输入描述

    The first line contains an integer number T, the number of test cases.
    For each test case:    
    The first line contains three integers n, m, k(), the number of A, the number of C and the value of k.
    The second line contains n integers ().
    The third line contains m integers ().

输出描述

For each test case print“YES”(without quotes) if it is possible, and“NO”(without quotes) otherwise.

示例1

输入: 

2
5 3 2
2 5 6 5 3
2 3 4
5 3 2
2 5 6 5 3
3 2 4

输出: 

YES
NO

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 1611ms, 内存消耗: 2244K, 提交时间: 2020-02-14 17:48:51 

#include <bits/stdc++.h>
 
using namespace std;
#define inf 0x3f3f3f3f
#define mid (l+r)/2
#define ls i*2+1
#define rs i*2+2
#define lson l,mid,ls
#define rson mid+1,r,rs
#define root 1,n,0
#define N 200005
int a[N*4],b[N],as[N];
void updata(int pos,int v,int l,int r,int i){
    if(l==r){
        a[i]=v;
        return ;
    }
    if(pos<=mid)updata(pos,v,lson);
    else updata(pos,v,rson);
    a[i]=min(a[ls],a[rs]);
}
 
int queryll(int v,int l,int r,int i){
    if(l==r)return l;
    if(a[rs]<=v)return queryll(v,rson);
    return queryll(v,lson);
}
 
int queryrr(int v,int l,int r,int i){
    if(l==r)return l;
    if(a[ls]<=v)return queryrr(v,lson);
    return queryrr(v,rson);
}
 
int queryl(int pos,int v,int l,int r,int i){
    if(pos>=r)return a[i]<=v?queryll(v,l,r,i):-1;
    if(pos<=mid)return queryl(pos,v,lson);
    int res=queryl(pos,v,rson);
    return res!=-1?res:queryl(pos,v,lson);
}
 
int queryr(int pos,int v,int l,int r,int i){
    if(pos<=l)return a[i]<=v?queryrr(v,l,r,i):-1;
    if(pos>mid)return queryr(pos,v,rson);
    int res=queryr(pos,v,lson);
    return res!=-1?res:queryr(pos,v,rson);
}
 
int main()
{
    int T,n,m,k;
    cin>>T;
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++){
            updata(i,inf,root);
            scanf("%d",&b[i]);
        }
        for(int i=1;i<=m;i++){
            scanf("%d",&as[i]);
            updata(as[i],b[as[i]],root);
        }
        int flag=1;
        for(int i=1;i<=m&&flag;i++){
            int l=as[i]!=1?queryl(as[i]-1,b[as[i]],root):-1;
            int r=as[i]!=n?queryr(as[i]+1,b[as[i]],root):-1;
            updata(as[i],inf,root);
            //cout<<l<<' '<<r<<endl;
            if(l==-1)l=0;
            if(r==-1)r=n+1;
            if(r-l<=k)flag=0;
        }
        if(flag)puts("YES");
        else puts("NO");
    }
}

C++14(g++5.4) 解法, 执行用时: 1681ms, 内存消耗: 22064K, 提交时间: 2019-05-13 20:16:16 

#include <bits/stdc++.h>

using namespace std;
#define inf 0x3f3f3f3f
#define mid (l+r)/2
#define ls i*2+1
#define rs i*2+2
#define lson l,mid,ls
#define rson mid+1,r,rs
#define root 1,n,0
#define N 200005
int a[N*4],b[N],as[N];
void updata(int pos,int v,int l,int r,int i){
    if(l==r){
        a[i]=v;
        return ;
    }
    if(pos<=mid)updata(pos,v,lson);
    else updata(pos,v,rson);
    a[i]=min(a[ls],a[rs]);
}

int queryll(int v,int l,int r,int i){
    if(l==r)return l;
    if(a[rs]<=v)return queryll(v,rson);
    return queryll(v,lson);
}

int queryrr(int v,int l,int r,int i){
    if(l==r)return l;
    if(a[ls]<=v)return queryrr(v,lson);
    return queryrr(v,rson);
}
int queryl(int L,int R,int v,int l,int r,int i){
    if(R<l||L>r)return -1;
    if(L<=l&&R>=r)return a[i]<=v?queryll(v,l,r,i):-1;
    int res=queryl(L,R,v,rson);
    return res!=-1?res:queryl(L,R,v,lson);
}
int queryr(int L,int R,int v,int l,int r,int i){
    if(R<l||L>r)return -1;
    if(L<=l&&R>=r)return a[i]<=v?queryrr(v,l,r,i):-1;
    int res=queryr(L,R,v,lson);
    return res!=-1?res:queryr(L,R,v,rson);
}


int main()
{
    int T,n,m,k;
    cin>>T;
    while(T--){
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++){
            updata(i,inf,root);
            scanf("%d",&b[i]);
        }
        for(int i=1;i<=m;i++){
            scanf("%d",&as[i]);
            updata(as[i],b[as[i]],root);
        }
        int flag=1;
        for(int i=1;i<=m&&flag;i++){
            int l=as[i]!=1?queryl(1,as[i]-1,b[as[i]],root):-1;
            int r=as[i]!=n?queryr(as[i]+1,n,b[as[i]],root):-1;
            updata(as[i],inf,root);
            //cout<<l<<' '<<r<<endl;
            if(l==-1)l=0;
            if(r==-1)r=n+1;
            if(r-l<=k)flag=0;
        }
        if(flag)puts("YES");
        else puts("NO");
    }
}

上一题

© 2025 nowcoder.com