Page Contents
Manhattan Subarrays Codeforces Solution
Suppose you have two points p=(xp,yp)p=(xp,yp) and q=(xq,yq)q=(xq,yq). Let’s denote the Manhattan distance between them as d(p,q)=|xp−xq|+|yp−yq|d(p,q)=|xp−xq|+|yp−yq|.
Let’s say that three points pp, qq, rr form a bad triple if d(p,r)=d(p,q)+d(q,r)d(p,r)=d(p,q)+d(q,r).
Let’s say that an array b1,b2,…,bmb1,b2,…,bm is good if it is impossible to choose three distinct indices ii, jj, kk such that the points (bi,i)(bi,i), (bj,j)(bj,j) and (bk,k)(bk,k) form a bad triple.
You are given an array a1,a2,…,ana1,a2,…,an. Calculate the number of good subarrays of aa. A subarray of the array aa is the array al,al+1,…,aral,al+1,…,ar for some 1≤l≤r≤n1≤l≤r≤n.
Note that, according to the definition, subarrays of length 11 and 22 are good.Input
The first line contains one integer tt (1≤t≤50001≤t≤5000) — the number of test cases.
The first line of each test case contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of array aa.
The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).
It’s guaranteed that the sum of nn doesn’t exceed 2⋅1052⋅105.Output
For each test case, print the number of good subarrays of array aa.
Example
input
3 4 2 4 1 3 5 6 9 1 9 6 2 13 37
output
10 12 3
Note
In the first test case, it can be proven that any subarray of aa is good. For example, subarray [a2,a3,a4][a2,a3,a4] is good since it contains only three elements and:
- d((a2,2),(a4,4))=|4−3|+|2−4|=3d((a2,2),(a4,4))=|4−3|+|2−4|=3 << d((a2,2),(a3,3))+d((a3,3),(a4,4))=3+1+2+1=7d((a2,2),(a3,3))+d((a3,3),(a4,4))=3+1+2+1=7;
- d((a2,2),(a3,3))d((a2,2),(a3,3)) << d((a2,2),(a4,4))+d((a4,4),(a3,3))d((a2,2),(a4,4))+d((a4,4),(a3,3));
- d((a3,3),(a4,4))d((a3,3),(a4,4)) << d((a3,3),(a2,2))+d((a2,2),(a4,4))d((a3,3),(a2,2))+d((a2,2),(a4,4));
In the second test case, for example, subarray [a1,a2,a3,a4][a1,a2,a3,a4] is not good, since it contains a bad triple (a1,1)(a1,1), (a2,2)(a2,2), (a4,4)(a4,4):
- d((a1,1),(a4,4))=|6−9|+|1−4|=6d((a1,1),(a4,4))=|6−9|+|1−4|=6;
- d((a1,1),(a2,2))=|6−9|+|1−2|=4d((a1,1),(a2,2))=|6−9|+|1−2|=4;
- d((a2,2),(a4,4))=|9−9|+|2−4|=2d((a2,2),(a4,4))=|9−9|+|2−4|=2;
So, d((a1,1),(a4,4))=d((a1,1),(a2,2))+d((a2,2),(a4,4))d((a1,1),(a4,4))=d((a1,1),(a2,2))+d((a2,2),(a4,4)).
Solution
#include <bits/stdc++.h>
using namespace std;
int a[200007];
int main() {
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
memset(a,0,sizeof(a));
for(int i=0;i<n;i++){
cin>>a[i];
}
long long ans=0;
ans+=n;
if(n>=2){
ans+=n-1;
if(n>=3){
for(int i=0;i<n-2;i++){
if(a[i+1]>max(a[i],a[i+2])||a[i+1]<min(a[i],a[i+2])){
ans++;
}
}
if(n>=4){
for(int i=0;i<n-3;i++){
if(a[i+1]>max(a[i],max(a[i+2],a[i+3]))&&a[i+2]<min(a[i],min(a[i+1],a[i+3]))||a[i+1]<min(a[i],min(a[i+2],a[i+3]))&&a[i+2]>max(a[i],max(a[i+1],a[i+3]))){
ans++;
}
}
}
}
}
cout<<ans<<endl;
}
return 0;
}
Educational Codeforces Round 111 (Rated for Div. 2)
- Excellent Arrays Codeforces Solution
- Stringforces Codeforces Solution
- Jumping Around Codeforces Solution
- Manhattan Subarrays Codeforces Solution
- Maximum Cost Deletion Codeforces Solution
- Find The Array Codeforces Solution
If some one needs expert view regarding blogging
then i suggest him/her to pay a quick visit this web site, Keep up
the good work.