### Brankonymous's blog

By Brankonymous, history, 13 months ago, ,

Hi, can someone help me solve this problem:

Input consist of integer n and array a of n integers. Output number of pairs (a[i],a[j]), i<j who are adjacent or for all k (i<k<j) this equation is true: a[k]<=min(a[i],a[j]).

1<=n<=10^6

0<=a[i]<=2^31

example:

8

4 1 2 3 6 5 1 2

Output: 11

• 0

 » 13 months ago, # | ← Rev. 2 →   -11 Since any adjacent element is considered as valid pair, ans is at least n-1. So initialize ans = n-1 Let the array be a[].For such index b where a[b+1] < a[b], if you use index b as left border, calculate how many index you can use as right border. From index b+1 iterate to the right til the elements are non decreasing, i.e. stop at index i when `a[i] using namespace std; const int maxn = 1000005; int a[maxn]; int main() { int n; cin>>n; for(int i=0;i>a[i]; long long ans = n-1; int b = -1; for(int i = 1;i<=n;i++){ if(i==n || (a[i] < a[i-1])){ if(b!=-1 && b < i-2){ //cout << i << ": " << i-2-b << "\n"; ans += i-b-2; } b = i-1; } else if(a[i]==a[i-1]){ int x = i-1; while(i+1
•  » » 13 months ago, # ^ |   0 If I understand you correctly, approach is wrong. If you see this test example: 5 4 2 3 2 5 Your answer will be 2 for i=1, you don't look pair (1,5), only (1,2),(1,3). I can't give you problem link beacuse I have problem written on paper, and problem is written on Serbian language.
•  » » » 13 months ago, # ^ |   -8 You are right. I didn't tested for this input. My bad.
 » 13 months ago, # |   -8 Can you give the problem link ?