Adi is the coach of his football team.
He wants to form a team in which there are two defenders and one striker
For this he will select two defenders from list A and one striker from B such that the strength of j th player is greater than ith player and strength of attacker is grater than both the defenders.
In other words A[ i ] < A[ j ] < B[ k ] and index i<j.
He is intersted in finding the number of teams
INPUT
First line contains an integer N denoting the size of list A and B.
Next line contain N space separated integers dentoing the array A.
Next line contain N space separated integers dentoing the array B .
OUTPUT
Find the number of teams possible such that A[ i ] <A[ j ] < B[ k] and i<j..
CONSTRAINT
He wants to form a team in which there are two defenders and one striker
For this he will select two defenders from list A and one striker from B such that the strength of j th player is greater than ith player and strength of attacker is grater than both the defenders.
In other words A[ i ] < A[ j ] < B[ k ] and index i<j.
He is intersted in finding the number of teams
INPUT
First line contains an integer N denoting the size of list A and B.
Next line contain N space separated integers dentoing the array A.
Next line contain N space separated integers dentoing the array B .
OUTPUT
Find the number of teams possible such that A[ i ] <A[ j ] < B[ k] and i<j..
CONSTRAINT
Explanation
Lời giải:
The possible teams are
(1,3,4), (1,2,3) , (1,2,3) ,(1,2,4), (1,3,4) , (2,3,4)
Note that these are values given not the index.
(1,3,4), (1,2,3) , (1,2,3) ,(1,2,4), (1,3,4) , (2,3,4)
Note that these are values given not the index.
#include<bits/stdc++.h> using namespace std; int main(){ int n,i,j,low,high,mid; cin>>n; long unsigned int a[n],b[n],val=0,k; for(i=0;i<n;i++) cin>>a[i]; for(i=0;i<n;i++) cin>>b[i]; sort(b,b+n); for(i=0;i<n;i++){ for(j=i+1;j<n;j++){ if(a[i]<a[j]){ if(b[0]>a[j]) val+=n; else if(b[n-1]<=a[j]) val+=0; else{ low=0;high=n-1; while(1){ mid=low+(high-low)/2; if(low==mid) break; if(b[mid]<(a[j]+1)) low=mid+1; else high=mid; } if(b[low]<=a[j]) low++; else if(low>0&&b[low-1]>a[j]) low--; val+=n-low; } } } } cout<<val; return 0; }
Không có nhận xét nào:
Đăng nhận xét