Kamrul13981

Untitled

Sep 11th, 2022 (edited)
1,153
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.62 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4.  
  5. #define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  6.  
  7. int main(){
  8.     Faster;
  9.     int t;                  
  10.     cin>>t;
  11.     while(t--)
  12.     {
  13.         int n;              
  14.         cin>>n;
  15.         vector<int>a(n),b(n),ta(n),tb(n);
  16.  
  17.         for(int i=0;i<n;i++){
  18.             cin>>a[i];
  19.             ta[i]=a[i];
  20.         }
  21.         for(int i=0;i<n;i++) {
  22.             cin>>b[i];
  23.             tb[i]=b[i];
  24.         }
  25.         // for(ll i=0;i<n;i++) {
  26.            
  27.         //     cout<<ta[i]<<" ";
  28.         // }
  29.  
  30.         sort(ta.begin(),ta.end());
  31.         sort(tb.begin(),tb.end());
  32.  
  33.         ta.erase(std::unique(ta.begin(),ta.end(),ta.end()));
  34.         tb.erase(std::unique(tb.begin(),tb.end(),tb.end()));
  35.  
  36.         for(int i=0;i<n;i++) {
  37.            a[i]=lower_bound(ta.begin(),ta.end(),a[i])-ta.begin();
  38.         }
  39.         for(int i=0;i<n;i++) {
  40.            b[i]=lower_bound(tb.begin(),tb.end(),b[i])-tb.begin();
  41.         }
  42.  
  43.         int temp=0,ans=0;
  44.  
  45.         vector<int>p(n),q(n),r,crr(n);
  46.  
  47.         for(int i=0;i<n;i++)
  48.         {
  49.             crr[a[i]]=b[i];
  50.             p[i]=a[i]+b[i];
  51.             q[b[i]]=i;
  52.         }
  53.         for(int i=0;i<n;i++)
  54.         {
  55.            r.insert(upper_bound(r.begin(),r.end(),crr[i]),crr[i]);
  56.            p[q[crr[i]]]-=lower_bound(r.begin(),r.end(),crr[i])-r.begin();
  57.         }
  58.  
  59.         for(auto i:p)
  60.         {
  61.             temp=max(i,temp);
  62.         }
  63.         for(auto i:p)
  64.         {
  65.             ans+=(i==temp);
  66.         }
  67.  
  68.         cout<<ans<<endl;
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.     }
  76.     return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment