fork download 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6. #pragma GCC target("avx2")
  7. #pragma GCC optimize("O3")
  8. #pragma GCC optimize("unroll-loops")
  9. typedef long long ll;
  10. typedef vector <ll> vll;
  11. typedef set <ll> sll;
  12. typedef vector <vector<ll>> vvll;
  13. typedef set<pair<ll,ll>> spll;
  14. typedef vector <bool> vbl;
  15. typedef vector <pair<ll,ll>> vpll;
  16. typedef map <ll,ll> mll;
  17.  
  18. #define yen cout<<"YES"<<"\n"
  19. #define ye cout<<"YES"
  20. #define non cout<<"NO"<<"\n"
  21. #define no cout<<"NO"
  22. #define pb push_back
  23. #define bk break
  24. #define co continue
  25. #define ff first
  26. #define ss second
  27. #define f(i, a, b) for (long long i = (a); i <= (b); i++)
  28. #define fr(i, a, b) for (long long i = (b); i >= (a); i--)
  29.  
  30. ll LMA=LLONG_MAX;
  31. ll LMI=LLONG_MIN;
  32.  
  33. void pr(vector <ll> &v)
  34. {
  35.     ll sz=v.size();
  36.     sz-=2;
  37.     for (ll i=1;i<=sz;i++)
  38.     {
  39.         cout<<v[i]<<" ";
  40.     }
  41.     cout<<"\n";
  42. }
  43.  
  44. void pr0(vector <ll> &v)
  45. {
  46.     for (auto elem:v)
  47.     {
  48.         cout<<elem<<" ";
  49.     }
  50.     cout<<"\n";
  51. }
  52.  
  53. template<typename T>
  54. using ordered_set = tree<
  55.     T,
  56.     null_type,
  57.     less<T>,
  58.     rb_tree_tag,
  59.     tree_order_statistics_node_update>;
  60.  
  61. int main()
  62. {
  63.     ios_base::sync_with_stdio(false);
  64.     cin.tie(0);
  65.  
  66.     ll t=1;
  67.     cin>>t;
  68.  
  69.     while (t--)
  70.     {
  71.         ll n;
  72.         cin>>n;
  73.         vll pref(n+2);
  74.         vll suf(n+2);
  75.         for (ll i=1;i<=n;i++)
  76.         {
  77.             cin>>pref[i];
  78.         }
  79.         for (ll i=1;i<=n;i++)
  80.         {
  81.             cin>>suf[i];
  82.         }
  83.         bool poss=true;
  84.         for (ll i=1;i<=(n-1);i++)
  85.         {
  86.             if (pref[i]>pref[i+1])
  87.             {
  88.                 poss=false;
  89.                 break;
  90.             }
  91.         }
  92.         for (ll i=n;i>=2;i--)
  93.         {
  94.             if (suf[i]>suf[i-1])
  95.             {
  96.                 poss=false;
  97.                 break;
  98.             }
  99.         }
  100.         if (!poss)
  101.         {
  102.             cout<<"NO"<<"\n";
  103.             continue;
  104.         }
  105.         ll ind=0;
  106.         for (ll i=1;i<=n;i++)
  107.         {
  108.             if (pref[i]!=0)
  109.             {
  110.                 ind=i;
  111.                 break;
  112.             }
  113.         }
  114.         for (ll i=n;i>=(ind+1);i--)
  115.         {
  116.             if (suf[i]!=0)
  117.             {
  118.                 poss=false;
  119.                 break;
  120.             }
  121.         }
  122.         if (!poss)
  123.         {
  124.             cout<<"NO"<<"\n";
  125.             continue;
  126.         }
  127.         for (ll i=1;i<=n;i++)
  128.         {
  129.             if (pref[i]>i)
  130.             {
  131.                 poss=false;
  132.                 break;
  133.             }
  134.         }
  135.         for (ll i=n;i>=1;i--)
  136.         {
  137.             if (suf[i]>(n-i+1))
  138.             {
  139.                 poss=false;
  140.                 break;
  141.             }
  142.         }
  143.         if (pref[n]!=n || suf[1]!=n)
  144.         {
  145.             poss=false;
  146.         }
  147.         if (!poss)
  148.         {
  149.             cout<<"NO"<<"\n";
  150.             continue;
  151.         }
  152.         vll answer(n+2,-1);
  153.         vbl vis(n+2,false);
  154.         for (ll i=n;i>=2;i--)
  155.         {
  156.             if (pref[i]!=pref[i-1])
  157.             {
  158.                 vis[pref[i-1]]=true;
  159.                 answer[i]=pref[i-1];
  160.             }
  161.         }
  162.         for (ll i=1;i<=(n-1);i++)
  163.         {
  164.             if (suf[i]!=suf[i+1])
  165.             {
  166.                 if (answer[i]== -1)
  167.                 {
  168.                     if (vis[suf[i+1]])
  169.                     {
  170.                         poss=false;
  171.                         break;
  172.                     } else if (!vis[suf[i+1]])
  173.                     {
  174.                         answer[i]=suf[i+1];
  175.                         vis[suf[i+1]]=true;
  176.                     }
  177.                 } else if (answer[i]!= -1)  // will only occur at index=ind. where, 0 will be there!
  178.                 {
  179.                     if (answer[i]!=suf[i+1])
  180.                     {
  181.                         poss=false;
  182.                         break;
  183.                     }
  184.                 }
  185.             }
  186.         }
  187.         if (!poss)
  188.         {
  189.             cout<<"NO"<<"\n";
  190.             continue;
  191.         }
  192.         cout<<"YES"<<"\n";
  193.     }
  194.  
  195.     return 0;
  196. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
1
1
1
1
stdout 
YES
https://ideone.com/hhbkjX
language:
C++14 (clang 8.0)
created:
199 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!