5E - Bindian Signalizing - CodeForces Solution

data structures *2400

Please click on ads to support us..

Python Code: 

n = int(input())
arr = [*map(int,input().split())]
i = arr.index(max(arr))
arr = arr[i:]+arr[:i]

stack,res = [[arr[0],1]],0
for j in range(1,n):
    if arr[j]>stack[-1][0]:
        while stack[-1][0]<arr[j]:
            res += stack.pop()[1]
    if arr[j]<stack[-1][0]: res += 1; stack += [arr[j],1],
    elif arr[j]==stack[-1][0]: res += stack[-1][1]+(len(stack)>1); stack[-1][1] += 1

if len(stack)>1 and stack[0][1]>1: res += stack[1][1]
for j in range(2,len(stack)): res += stack[j][1]
print(res)

C++ Code: 

#include <bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 10;
int a[maxn], b[maxn], l[maxn], r[maxn], s[maxn];

int main() {
    int n, maxn, po;
    cin >> n;

    for (int i = 0; i < n; i++)
        cin >> a[i];
    
    maxn = a[0];
    po = 0;

    for (int i = 1; i < n; i++) {
        if (a[i] > maxn) {
            maxn = a[i];
            po = i;
        }
    }

    for (int i = 0; i < n; i++)
        b[i] = a[(po + i) % n];
    
    b[n] = b[0];
    s[n] = 0;
    
    for (int i = n - 1; i >= 0; i--) {
        r[i] = i + 1;

        while (r[i] < n && b[i] > b[r[i]])
            r[i] = r[r[i]];
        
        while (r[i] < n && b[i] == b[r[i]]) {
            s[i] = s[r[i]] + 1;
            r[i] = r[r[i]];
        }
    }

    l[0] = 0;
    
    for (int i = 1; i < n; i++) {
        l[i] = i - 1;

        while (l[i] > 0 && b[i] >= b[l[i]])
            l[i] = l[l[i]];
    }

    long long ans = 0;
    
    for (int i = 0; i < n; i++) {
        ans += s[i];

        if (b[i] < b[0]) {
            if (l[i] == 0 && r[i] == n) ans += 1;
            else ans += 2;
        }
    }

    cout << ans;

    return 0;
}


Comments

Submit
0 Comments
More Questions

1478B - Nezzar and Lucky Number
228A - Is your horseshoe on the other hoof
122A - Lucky Division
1611C - Polycarp Recovers the Permutation
432A - Choosing Teams
758A - Holiday Of Equality
1650C - Weight of the System of Nested Segments
1097A - Gennady and a Card Game
248A - Cupboards
1641A - Great Sequence
1537A - Arithmetic Array
1370A - Maximum GCD
149A - Business trip
34A - Reconnaissance 2
59A - Word
462B - Appleman and Card Game
1560C - Infinity Table
1605C - Dominant Character
1399A - Remove Smallest
208A - Dubstep
1581A - CQXYM Count Permutations
337A - Puzzles
495A - Digital Counter
796A - Buying A House
67A - Partial Teacher
116A - Tram
1472B - Fair Division
1281C - Cut and Paste
141A - Amusing Joke
112A - Petya and Strings