Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- #define nl "\n"
- #define fi first
- #define se second
- #define pb push_back
- #define ll long long
- #define ull unsigned ll
- #define RV return void
- // #define inf 2000000000
- #define sz(x) int(x.size())
- #define all(v) v.begin(), v.end()
- #define rall(v) v.rbegin(), v.rend()
- #define Mini(x) *min_element(all(x))
- #define Maxi(x) *max_element(all(x))
- #define fixed(n) fixed << setprecision(n)
- #define ceil(w, m) (((w) / (m)) + ((w) % (m) ? 1 : 0))
- #define cin(v) for (auto&i:v) cin >> i;
- #define cout(v) for (auto&i:v) cout << i << " ";
- #define clr(memo, x) memset(memo, x, sizeof memo)
- #define updmin(a, b) a = min(a, b)
- #define updmax(a, b) a = max(a, b)
- #define vi vector < int >
- #define vl vector < ll >
- #define vc vector < char >
- #define vs vector < string >
- #define v2i vector < vector < int > >
- #define v2l vector < vector < int > >
- #define seti set < int >
- #define setl set < ll >
- #define mapii map < int , int >
- #define mapll map < ll , ll >
- #define mapli map < ll , int >
- #define mapci map < char , int >
- #define mapsi map < string , int >
- #define pll pair < ll , ll >
- #define pii pair < int , int >
- #define range(l,r,x) for(int i=l ; i < r ; i+=x)
- #define FastCode ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
- vector < string > ternary= {"No\n" , "Yes\n"};
- void Zainab(){
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- }
- /*================================ solution ================================ */
- const ll inf = 1e18;
- struct segTree{
- int size =1;
- vector < ll > Min;
- void init(int n){
- while(size < n ) size *=2;
- Min.assign(2*size , inf);
- }
- void set(int idx , ll val , int node , int lx , int rx){
- if(rx - lx == 1 ){
- // cout << idx << ' ' << node << " " << val << nl;
- Min[node] = val;
- return ;
- }
- int mid = rx - (rx - lx)/2 ;
- if(idx < mid ){
- set(idx , val , 2 * node , lx , mid);
- }else{
- set(idx , val , 2 * node + 1 , mid , rx);
- }
- Min[node] = min(Min[2 * node] , Min[2 * node + 1 ]);
- }
- void set(int idx , ll val){
- return set(idx , val , 1 , 1 , size );
- }
- void build(const vector <ll> & v , int node , int lx , int rx){
- if(rx - lx ==1 ){
- if( lx < sz(v) )
- Min[node] = v[lx];
- return ;
- }
- int mid = rx - (rx-lx)/2;
- build(v , 2*node , lx , mid);
- build(v , 2*node +1 , mid , rx);
- Min[node] = min(Min[node*2] , Min[node*2+1]);
- }
- void build(const vector<ll>&v ){
- build(v , 1 , 1 , size);
- }
- ll get(int l , int r , int node , int lx , int rx){
- if(lx >= l and rx <= r) return Min[node];
- if(l >= rx or r <= lx) return inf;
- int mid = rx - (rx-lx)/2;
- return min(get(l , r , 2*node , lx , mid) , get(l , r , 2*node+1 , mid , rx));
- }
- ll get(int l , int r ){
- return get(l , r , 1 , 1 , size);
- }
- };
- void myCode(){
- int n ;
- cin >> n ;
- vector < ll > a(n) , b(n+1);
- for(int i =0 ; i < n ; i++) cin >> a[i];
- for(int i =1 ; i <= n ; i++) cin >> b[i];
- segTree seg ;
- seg.init(n+1);
- seg.build(b);
- vector < ll > next_greater(n);
- stack < int > st;
- for(int i = n -1; i >= 0; i--){
- while(!st.empty() and a[st.top()] <= a[i]) st.pop();
- next_greater[i] = (st.empty() ? -1 : st.top());
- st.push(i);
- }
- // cout(next_greater);
- vector < ll > prev_greater(n);
- while(!st.empty()) st.pop();
- for(int i = 0; i < n; i++){
- while(!st.empty() and a[st.top()] <= a[i]) st.pop();
- prev_greater[i] = (st.empty() ? -1 : st.top());
- st.push(i);
- }
- // cout (prev_greater);
- vector< vector<int> > vms(n+1);
- for(int i =1 ; i <= n ; i++){
- vms[b[i]].pb(i-1);
- }
- for(int i =0 ; i < n ; i++){
- if(a[i] == b[i+1] ) continue;
- if(a[i] > b[i+1] ) RV(cout << "NO\n");
- // after
- auto idx = upper_bound(all(vms[b[i+1]]) , i);
- if(idx != vms[b[i+1]].end()){
- if(seg.get(i + 1 , *idx + 1) == b[i+1] and
- (next_greater[a[i]] > *idx or next_greater[a[i]] == -1))
- continue;
- }
- if(idx != vms[b[i+1]].begin()){
- idx--;
- if(seg.get(*idx+1 , i+1) == b[i+1] and
- (prev_greater[a[i]] < *idx or prev_greater[a[i]] ==-1 ) )
- continue;
- }
- RV(cout << "NO\n");
- }
- cout << "YES\n";
- }
- int main(){
- FastCode ;
- // Zainab() ;
- int testCase=1;
- cin >> testCase ;
- for(int i=1 ; i<= testCase ; i++){
- // cout << "Case #" << i << ": ";
- myCode();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement