专栏首页glm的全栈学习之路Codeforces Round #624 (Div. 3) B - WeirdSort

Codeforces Round #624 (Div. 3) B - WeirdSort

B - WeirdSort

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an array aa of length nn.

You are also given a set of distinct positions p1,p2,…,pmp1,p2,…,pm, where 1≤pi<n1≤pi<n. The position pipi means that you can swap elements a[pi]a[pi] and a[pi+1]a[pi+1]. You can apply this operation any number of times for each of the given positions.

Your task is to determine if it is possible to sort the initial array in non-decreasing order (a1≤a2≤⋯≤ana1≤a2≤⋯≤an) using only allowed swaps.

For example, if a=[3,2,1]a=[3,2,1] and p=[1,2]p=[1,2], then we can first swap elements a[2]a[2] and a[3]a[3] (because position 22 is contained in the given set pp). We get the array a=[3,1,2]a=[3,1,2]. Then we swap a[1]a[1] and a[2]a[2] (position 11 is also contained in pp). We get the array a=[1,3,2]a=[1,3,2]. Finally, we swap a[2]a[2] and a[3]a[3] again and get the array a=[1,2,3]a=[1,2,3], sorted in non-decreasing order.

You can see that if a=[4,1,2,3]a=[4,1,2,3] and p=[3,2]p=[3,2] then you cannot sort the array.

You have to answer tt independent test cases.

Input

The first line of the input contains one integer tt (1≤t≤1001≤t≤100) — the number of test cases.

Then tt test cases follow. The first line of each test case contains two integers nn and mm (1≤m<n≤1001≤m<n≤100) — the number of elements in aa and the number of elements in pp. The second line of the test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1001≤ai≤100). The third line of the test case contains mm integers p1,p2,…,pmp1,p2,…,pm (1≤pi<n1≤pi<n, all pipi are distinct) — the set of positions described in the problem statement.

Output

For each test case, print the answer — "YES" (without quotes) if you can sort the initial array in non-decreasing order (a1≤a2≤⋯≤ana1≤a2≤⋯≤an) using only allowed swaps. Otherwise, print "NO".

Example

input

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

output

YES
NO
YES
YES
NO
YES

此题有很多做法,我用的是并查集,其实也可以用冒泡排序的思想来做,最后再检查是否有序即可

并查集的思路也很简单就是题目给的可交换的下标都可以合在一起,然后去检查排好序之后的下标和原先的下标是不是在一个集合内就ok了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register ll
#define inf 2147483647
#define lb(x) (x&(-x))
ll sz[200005],n;
template <typename T> inline void read(T& x)
{
    x=0;char ch=getchar();ll f=1;
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}x*=f;
}
inline ll query(ll x){ll res=0;while(x){res+=sz[x];x-=lb(x);}return res;}
inline void add(ll x,ll val){while(x<=n){sz[x]+=val;x+=lb(x);}}//第x个加上val
struct node
{
    ll val,pos;
}p[105];
inline bool cmp(const node&a,const node&b)
{
    if(a.val==b.val)return a.pos<b.pos;
    return a.val<b.val;
}
ll t,f[105],q[105];
inline void init(ll m)
{
    memset(f,0,sizeof(f));
    for(rg i=1;i<=100;i++)f[i]=i;
}
inline ll fa(ll x)
{
    return f[x]==x?x:f[x]=fa(f[x]);
}
inline void merge(ll x,ll y)
{
    ll fx=fa(x),fy=fa(y);
    if(fx!=fy)
    {
        f[fy]=fx;
    }
}
int main()
{
	cin>>t;
    for(rg i=1;i<=t;i++)
    {
        ll n,m,sum=0;
        cin>>n>>m;
        init(m);
        for(rg i=1;i<=n;i++)cin>>p[i].val,p[i].pos=i;
        for(rg j=1;j<=m;j++)cin>>q[j],merge(q[j],q[j]+1);
        sort(p+1,p+1+n,cmp);
        for(rg j=1;j<=n;j++)
        {
            if(fa(p[j].pos)==fa(j))
            {
                sum++;
            }
        }
        sum==n?cout<<"YES"<<endl:cout<<"NO"<<endl;
    }
    while(1)getchar();
    return 0;
    
}
/*
3 2 1
1 2
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Codeforces Round #633 (Div. 2) A Filling Diamonds (假题,观察)

    You have integer nn. Calculate how many ways are there to fully cover belt-like ...

    glm233
  • Codeforces Round #424 (Div. 1, rated, based on VK Cup Finals) B. Cards Sorting 树状数组+技巧

    Vasily has a deck of cards consisting of n cards. There is an integer on each of...

    glm233
  • PAT (Advanced Level) Practice 1146 Topological Order (25分)

    This is a problem given in the Graduate Entrance Exam in 2018: Which of the foll...

    glm233
  • Access the OData service exposed by your CDS view via Smart Business Tile

    It is possible to configure a Smart business tile which consumes the OData servi...

    Jerry Wang
  • 使用SAP S/4HANA Smart Business Tile消费CDS view OData服务

    版权声明:本文为博主汪子熙原创文章,未经博主允许不得转载。 https://jerry.bl...

    Jerry Wang
  • 遇到SAP WebClient UI的白屏错误,应该如何分析?

    I have already written one blog How to persist the ui exception so you can view ...

    Jerry Wang
  • 2014---多校训练一(A Couple doubi)

    Couple doubi Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768...

    Gxjun
  • Codeforces Round #408 (Div. 2)(A.水,B,模拟)

    A. Buying A House time limit per test:2 seconds memory limit per test:256 megaby...

    Angel_Kitty
  • python 卷积函数_用Python计算两个函数的卷积

    What is a convolution? OK, that’s not such a simple question. Instead, I am will...

    用户7886150
  • 如何修复破碎的手机或平板电脑屏幕( mobile tech smartphone)

    如何修复破碎的手机或平板电脑屏幕( mobile tech  smartphone)

    木樾233

扫码关注云+社区

领取腾讯云代金券