Guest User

Untitled

a guest
Apr 19th, 2018
390
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.24 KB | None | 0 0
  1. /*
  2.  *
  3.  ********************************************************************************************
  4.  * AUTHOR : Vijju123                                                                        *
  5.  * Language: C++14                                                                          *
  6.  * Purpose: -                                                                               *
  7.  * IDE used: Codechef IDE.                                                                  *
  8.  ********************************************************************************************
  9.  *
  10.  Comments will be included in practice problems if it helps ^^
  11.  */
  12.  
  13.  
  14.  
  15. #include <iostream>
  16. #include<bits/stdc++.h>
  17. using namespace std;
  18.  
  19. int main() {
  20.     // your code goes here
  21.     #ifdef JUDGE
  22.     freopen("input.txt", "rt", stdin);
  23.     freopen("output.txt", "wt", stdout);
  24.     #endif
  25.     ios_base::sync_with_stdio(0);
  26.     cin.tie(NULL);
  27.     cout.tie(NULL);
  28.     int t;
  29.     cin>>t;
  30.     while(t--)
  31.     {
  32.         int n;
  33.         cin>>n;
  34.         int a[n],b[n],ans=0;
  35.         int i,j;
  36.         //Input
  37.         for(i=0;i<n;i++)
  38.             cin>>a[i];
  39.         for(i=0;i<n;i++)
  40.             cin>>b[i];
  41.  
  42.         deque<int> q;
  43.         int possible=1;
  44.         //Check for case of -1 first.
  45.         for(i=0;i<n;i++)
  46.         {
  47.             if(a[i]<b[i])
  48.             {
  49.                 possible=0;
  50.                 break;
  51.             }
  52.         }
  53.         if(possible==0)cout<<-1<<endl;
  54.         else
  55.         {
  56.             for(i=0;i<n;i++)
  57.             {
  58.                 while(!q.empty() and q.back()<b[i])//If there are any recently inserted plants less than b[i]
  59.                     q.pop_back();
  60.                 while(!q.empty() and q.front()>a[i])//If height of any previous b[j] is less than current a[i].
  61.                     q.pop_front();//Please note, that due to our prev. while loop, deque has b[i] in descending
  62.                     //order.
  63.                 if( a[i]!=b[i] and (q.empty() or b[i]!=q.back()) )
  64.                 {
  65.                     ans++;//We cannot find 2 equal b[i] :( . Hence, will need to do 1 more operation.
  66.                     q.push_back(b[i]);
  67.                 }
  68.             }
  69.             cout<<ans<<endl;
  70.         }
  71.  
  72.     }
  73.  
  74.     return 0;
  75. }
Add Comment
Please, Sign In to add comment