Advertisement
RaFiN_

obtain array b from array a by sorting a range any number of

Jul 1st, 2019
163
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.73 KB | None | 0 0
  1. /* obtain array b from array a by sorting a range any number of times in a */
  2.  
  3. /* the trick will be to use sort opportunity as to sort two adjacent element so that a number comes to pos a from pos b without changing relative order of other elements */
  4. void update(int node,int st,int en,int pos,int v)
  5. {
  6.     if(st>pos or en<pos)return ;
  7.     if(st==en)
  8.     {
  9.         tree[node]=v;
  10.         return ;
  11.     }
  12.     int mid=(st+en)>>1;
  13.     update(node*2,st,mid,pos,v);
  14.      update(node*2+1,mid+1,en,pos,v);
  15.     tree[node]=min(tree[node*2],tree[node*2+1]);
  16. }
  17. int query(int node,int st,int en,int l,int r)
  18. {
  19.        if(st>r or en<l)return INT_MAX;
  20.        if(st>=l and en<=r)return tree[node];
  21.        int mid=(st+en)>>1;
  22.        int v=query(node*2,st,mid,l,r);
  23.        int w=query(node*2+1,mid+1,en,l,r);
  24.        return min(v,w);
  25. }
  26. vector<int>s[mx];
  27. int main()
  28. {
  29.     int i,j,k,l,m,n;
  30.     scanf("%d",&m);
  31.     while(m--)
  32.     {
  33.         scanf("%d",&n);
  34.         for(int i=1;i<=n;i++)s[i].clear();
  35.         for(int i=1;i<=n;i++)
  36.         {
  37.             scanf("%d",&ara[i]);
  38.             update(1,1,n,i,ara[i]);
  39.             s[ara[i]].pb(i);
  40.         }
  41.         for(int i=1;i<=n;i++)sort(s[i].rbegin(),s[i].rend());
  42.         for(int i=1;i<=n;i++)
  43.         {
  44.            scanf("%d",&bara[i]);
  45.         }
  46.         int ck=1;
  47.         for(int i=1;i<=n;i++)
  48.         {
  49.  
  50.             int l=bara[i];
  51.             if(s[l].size()==0)
  52.             {
  53.                 ck=0;
  54.                 break;
  55.             }
  56.             int p=s[l][s[l].size()-1];
  57.             s[l].pop_back();
  58.             int k=query(1,1,n,1,p-1);
  59.             if(k<l)ck=0;
  60.             update(1,1,n,p,INT_MAX);
  61.         }
  62.         if(ck)printf("YES\n");
  63.         else printf("NO\n");
  64.     }
  65.  
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement