fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. using namespace __gnu_pbds;
  4. using namespace std;
  5. #define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6.  
  7. typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
  8. typedef tree<long long,null_type,less_equal<long long>,rb_tree_tag,tree_order_statistics_node_update> multi_indexed_set;
  9.  
  10.  
  11. const int N=1e6+2;
  12. const int M=1e9+7;
  13. long long NN=316,MM,S,K;
  14. long long test_case; 
  15.  
  16. #define ll long long
  17. #define lp(i,a,b) for(ll i=a;i<=b;i++)
  18. #define rlp(i,a,b) for(ll i=a;i>=b;i--)
  19. #define vec vector<long long>
  20. #define pb push_back
  21. #define rpb pop_back
  22. #define f first
  23. #define s second
  24. #define el "\n"
  25. #define pri(ara,n) for(ll i=1;i<=n;i++)cout<<ara[i]<<" ";cout<<el;
  26. #define priv(vec) for(auto va:vec)cout<<va<<" ";cout<<"\n";
  27. #define srt(ara,n) sort(ara+1,ara+1+n);
  28. #define srtv(vec) sort(vec.begin(), vec.end());
  29. #define revv(vec) reverse(vec.begin(), vec.end());
  30. #define coutl cout<<"Case "<<test_case<<": "
  31. #define in(ara,n) cin>>n;lp(i,1,n)cin>>ara[i];
  32. #define all(ara,n,m) lp(i,1,n)ara[i]=m;
  33. #define index(indexed_Set,val) indexed_Set.order_of_key(val)
  34. #define value(indexed_Set,ind) *indexed_Set.find_by_order(ind) 
  35. #define pi 2*acos(0.0)
  36. #define Mems(dp,n) memset(dp,n,sizeof(dp))
  37.  
  38. bool myComparison(const pair<pair<ll,ll>,ll> &a,const pair<pair<ll,ll>,ll> &b)  // for vector sorting  1st element small to learge (if same then second element large to small)
  39. {
  40.     if(a.f.f==b.f.f)return a.f.s>b.f.s;
  41.     else return a.f.f<b.f.f;
  42. }
  43. bool cmp1(const pair<ll,ll> &a,const pair<ll,ll> &b)    // for vector sorting  1st element small to learge (if same then second element large to small)
  44. {
  45.     // return a>b;
  46.     if(a.f==b.f)return a.s<b.s;
  47.     else return a.f>b.f;
  48. }
  49.  
  50. ll lcm(ll a,ll b)
  51. {
  52.     return (a*b)/(__gcd(a,b));
  53. }
  54. ll gcd(ll a,ll b) 
  55. {
  56.     return __gcd(a,b);
  57. }
  58.  
  59.  
  60. //ll arr[1001][1001];
  61.  
  62.  
  63.  
  64.  
  65. ll  ara[N],ara1[N],indx[N],vis[N];
  66.  
  67. vector<ll>v[N];
  68.  
  69.  
  70.  
  71.  
  72.  
  73. ll  input[N],store_sum_data_for_seg_tree[N];
  74. // vector<ll>v[N];
  75. //vector<ll>v(N),inv(N);
  76. //ll arr[1001][1001];
  77.  
  78. ll built_sum_seg_tree(ll a,ll b,ll n)
  79. {
  80.     if(a==b)return store_sum_data_for_seg_tree[n]=input[a];
  81.     ll mid=(a+b)/2;
  82.     return store_sum_data_for_seg_tree[n]=(built_sum_seg_tree(a,mid,2*n)+built_sum_seg_tree(mid+1,b,2*n+1));
  83. }
  84.  
  85. ll find_sum_from_seg_tree(ll x,ll y,ll a,ll b,ll n) // first two variable is my range for finding sum
  86. {
  87.     if(b<x||a>y)return 0;
  88.     if(a>=x&&b<=y)return store_sum_data_for_seg_tree[n];
  89.     ll mid=(a+b)/2;
  90.     return (find_sum_from_seg_tree(x,y,a,mid,2*n)+find_sum_from_seg_tree(x,y,mid+1,b,2*n+1));
  91. }
  92.  
  93. ll change_value_in_seg_tree(ll in,ll va,ll a,ll b,ll n)
  94. {
  95.     if(in<a||in>b)return store_sum_data_for_seg_tree[n];
  96.     if(a==b)return store_sum_data_for_seg_tree[n]=(input[a]-va);
  97.     ll mid=(a+b)/2;
  98.     return store_sum_data_for_seg_tree[n]=(change_value_in_seg_tree(in,va,a,mid,2*n)+change_value_in_seg_tree(in,va,mid+1,b,2*n+1));   
  99. }
  100.  
  101.  
  102.  
  103.  
  104. void solve()
  105. {
  106.     ll i,j,k,l,m,n,o,p,q,r,t,a,b,h,c,d,e,f,x,y,z,ans,ans1;
  107.     cin>>n>>m>>k;
  108.  
  109.     lp(i,0,4*n)input[i]=store_sum_data_for_seg_tree[i]=0;
  110.  
  111.     built_sum_seg_tree(1,n,1);
  112.  
  113.  
  114.  
  115.     lp(i,1,n)vis[i]=0;
  116.     lp(i,1,n)
  117.     {
  118.         cin>>ara[i];
  119.         indx[ara[i]]=i;
  120.     }
  121.     lp(i,1,m)
  122.     {
  123.  
  124.         cin>>ara1[i];
  125.         vis[ara1[i]]=1;
  126.     }
  127.     ll flag=0;
  128.  
  129.     lp(i,1,m-1)
  130.     {
  131.         if(indx[ara1[i]]>indx[ara1[i+1]])flag=1;
  132.     }
  133.     if(flag)
  134.     {
  135.         cout<<"NO"<<el;
  136.         return;
  137.     }
  138.  
  139.     set<ll>st;
  140.     st.insert(0);
  141.     st.insert(n+1);
  142.  
  143.     multiset<ll>mul_st;
  144.     lp(i,1,k)
  145.     {
  146.         cin>>a;
  147.         mul_st.insert(a);
  148.     }
  149.  
  150.     rlp(i,n,1)
  151.     {
  152.         if(vis[i])
  153.         {
  154.             st.insert(indx[i]);
  155.         }
  156.         else
  157.         {
  158.             a=indx[i];
  159.             auto va=st.upper_bound(a);
  160.             ll up=(*va);
  161.             ll dn=(*(--va));
  162.  
  163.             ll len=up-dn-1;
  164.  
  165.             ll tem1=find_sum_from_seg_tree(dn+1,up-1,1,n,1);
  166.             len-=tem1;
  167.  
  168.             auto va1=mul_st.upper_bound(len);
  169.  
  170.             if(va1==mul_st.begin())
  171.             {
  172.                 cout<<"NO"<<el;
  173.                 return;
  174.             } 
  175.             va1--;
  176.  
  177.             mul_st.erase(va1);
  178.  
  179.             // st.insert(indx[i]);
  180.  
  181.             change_value_in_seg_tree(indx[i],-1,1,n,1);
  182.  
  183.         }
  184.     }
  185.  
  186.     cout<<"YES"<<el;
  187. }
  188.  
  189. int main()
  190. {
  191.     fast;
  192.     ll t=1;
  193.     cin>>t;
  194.     test_case=1;
  195.     while(t--)
  196.     {
  197.         solve();
  198.         test_case++;
  199.     }
  200. }
Success #stdin #stdout 0.01s 36356KB
comments (?)
stdin
copy 
3
5 2 3
5 1 3 2 4
5 2
1 2 4
5 5 5
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5
4 2 1
4 3 2 1
4 1
1
stdout
copy 
YES
YES
NO
https://ideone.com/gpjj5Z
language:
C++14 (gcc 8.3)
created:
81 days ago
visibility:
public

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!