Advertisement
Zeinab_Hamdy

Untitled

Dec 10th, 2023
866
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.55 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define nl "\n"
  4. #define fi first
  5. #define se second
  6. #define pb push_back
  7. #define ll long long
  8. #define ull unsigned ll
  9. #define RV  return void
  10. // #define inf 2000000000
  11. #define sz(x) int(x.size())
  12. #define all(v) v.begin(), v.end()
  13. #define rall(v) v.rbegin(), v.rend()
  14. #define Mini(x) *min_element(all(x))
  15. #define Maxi(x) *max_element(all(x))
  16. #define fixed(n) fixed << setprecision(n)
  17. #define ceil(w, m) (((w) / (m)) + ((w) % (m) ? 1 : 0))
  18. #define cin(v) for (auto&i:v) cin >> i;
  19. #define cout(v) for (auto&i:v) cout << i << " ";
  20. #define clr(memo, x) memset(memo, x, sizeof memo)
  21. #define updmin(a, b) a = min(a, b)
  22. #define updmax(a, b) a = max(a, b)
  23. #define vi vector < int >
  24. #define vl vector < ll >
  25. #define vc vector < char >
  26. #define vs vector < string >
  27. #define v2i vector < vector < int > >
  28. #define v2l vector < vector < int > >
  29. #define seti set < int >
  30. #define setl set < ll >
  31. #define mapii map < int , int >
  32. #define mapll map < ll , ll >
  33. #define mapli map < ll , int >
  34. #define mapci map < char , int >
  35. #define mapsi map < string , int >
  36. #define pll pair < ll , ll >
  37. #define pii pair < int , int >
  38. #define range(l,r,x) for(int i=l ; i < r ; i+=x)
  39. #define FastCode ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  40. vector < string > ternary= {"No\n" , "Yes\n"};
  41.  
  42. void  Zainab(){
  43.             #ifndef ONLINE_JUDGE
  44.               freopen("input.txt", "r", stdin);
  45.               freopen("output.txt", "w", stdout);
  46.             #endif
  47. }
  48.  
  49.  
  50. /*================================  solution  ================================ */
  51.  
  52.  
  53. const ll inf = 1e18;
  54. struct segTree{
  55.    
  56.     int size =1;
  57.     vector < ll > Min;
  58.    
  59.     void init(int n){
  60.         while(size < n ) size *=2;
  61.        
  62.         Min.assign(2*size , inf);
  63.     }
  64.    
  65.    
  66.     void set(int idx , ll val , int node , int lx , int rx){
  67.         if(rx - lx == 1 ){
  68.             // cout << idx << ' ' << node << " " << val << nl;
  69.            
  70.             Min[node] = val;
  71.             return ;
  72.         }
  73.        
  74.         int mid = rx - (rx - lx)/2 ;
  75.        
  76.         if(idx < mid ){
  77.             set(idx , val , 2 * node  , lx , mid);
  78.         }else{
  79.             set(idx , val , 2 * node + 1 , mid , rx);
  80.         }
  81.        
  82.         Min[node] = min(Min[2 * node] , Min[2 * node + 1 ]);
  83.     }
  84.    
  85.     void set(int idx , ll val){
  86.         return set(idx , val , 1 , 1 , size );
  87.     }
  88.    
  89.     void build(const vector <ll> & v , int node , int lx , int rx){
  90.        
  91.         if(rx - lx ==1 ){
  92.             if( lx < sz(v) )
  93.                 Min[node] = v[lx];
  94.                
  95.             return ;
  96.         }
  97.        
  98.         int mid = rx - (rx-lx)/2;
  99.        
  100.         build(v , 2*node , lx , mid);
  101.         build(v , 2*node +1 , mid , rx);
  102.        
  103.         Min[node] = min(Min[node*2] , Min[node*2+1]);
  104.        
  105.     }
  106.    
  107.     void build(const vector<ll>&v ){
  108.         build(v , 1 , 1 , size);
  109.     }
  110.    
  111.    
  112.     ll get(int l , int r , int node , int lx , int rx){
  113.         if(lx >= l and rx <= r) return Min[node];
  114.        
  115.         if(l >= rx or r <= lx) return inf;
  116.        
  117.         int mid = rx - (rx-lx)/2;
  118.        
  119.         return min(get(l , r , 2*node , lx , mid) , get(l , r , 2*node+1 , mid , rx));
  120.     }
  121.    
  122.     ll get(int l , int r ){
  123.         return get(l , r , 1 , 1 , size);
  124.     }
  125. };
  126.  
  127. void myCode(){
  128.  
  129.  
  130.     int n ;
  131.     cin >> n ;
  132.     vector < ll > a(n) , b(n+1);
  133.     for(int i =0 ; i < n ; i++) cin >> a[i];
  134.     for(int i =1 ; i <= n ; i++) cin >> b[i];
  135.    
  136.     segTree seg ;
  137.     seg.init(n+1);
  138.  
  139.    
  140.     seg.build(b);
  141.    
  142.    
  143.    
  144.  
  145.         vector < ll > next_greater(n);
  146.         stack < int > st;
  147.         for(int i = n -1;  i >= 0; i--){
  148.             while(!st.empty() and a[st.top()] <= a[i]) st.pop();
  149.             next_greater[i] = (st.empty() ? -1 : st.top());
  150.             st.push(i);
  151.         }
  152.        
  153.         // cout(next_greater);
  154.        
  155.         vector < ll > prev_greater(n);
  156.         while(!st.empty()) st.pop();
  157.        
  158.         for(int i = 0; i < n; i++){
  159.             while(!st.empty() and a[st.top()] <= a[i]) st.pop();
  160.             prev_greater[i] = (st.empty() ? -1 : st.top());
  161.             st.push(i);
  162.         }
  163.        
  164.         // cout (prev_greater);
  165.        
  166.         vector< vector<int> > vms(n+1);
  167.        
  168.         for(int i =1 ; i  <= n ; i++){
  169.             vms[b[i]].pb(i-1);
  170.         }
  171.        
  172.        
  173.         for(int i =0 ; i < n ; i++){
  174.             if(a[i] == b[i+1] ) continue;
  175.             if(a[i] > b[i+1] ) RV(cout << "NO\n");
  176.            
  177.            
  178.             // after
  179.            
  180.             auto idx = upper_bound(all(vms[b[i+1]]) , i);
  181.            
  182.             if(idx != vms[b[i+1]].end()){
  183.                 if(seg.get(i + 1 , *idx + 1) == b[i+1] and
  184.                     (next_greater[a[i]] > *idx or next_greater[a[i]] == -1))
  185.                     continue;
  186.             }
  187.  
  188.  
  189.             if(idx != vms[b[i+1]].begin()){
  190.                      idx--;
  191.                     if(seg.get(*idx+1 , i+1) == b[i+1] and
  192.                     (prev_greater[a[i]] < *idx or prev_greater[a[i]] ==-1 )  )
  193.                          continue;
  194.             }
  195.  
  196.  
  197.              RV(cout << "NO\n");
  198.            
  199.         }
  200.        
  201.        
  202.         cout << "YES\n";
  203.        
  204.        
  205. }
  206.  
  207. int main(){
  208.  
  209.         FastCode ;
  210.         // Zainab() ;
  211.  
  212.         int testCase=1;
  213.             cin >> testCase ;
  214.         for(int i=1 ; i<= testCase ; i++){
  215.             //  cout << "Case #" << i << ": ";
  216.             myCode();
  217.         }
  218.      
  219.  
  220.     return 0;
  221. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement