Cerinta completa

Shik loves sorted intervals. But currently he does not have enough time to sort all the numbers. So he decided to use Almost sorted intervals. An Almost sorted interval is a consecutive subsequence in a sequence which satisfies the following property:

  1. The first number is the smallest.
  2. The last number is the largest.

Please help him count the number of almost sorted intervals in this permutation.

Note: Two intervals are different if at least one of the starting or ending indices are different.

Input Format
The first line contains an integer N.
The second line contains a permutation from 1 to N.

Output Format
Output the number of almost sorted intervals.

Constraints
1 ≤ N ≤ 106

Sample Input 

5
3 1 2 5 4

Sample Output 

8

Explanation
The subsequences [3], [1], [1 2], [1 2 5], [2], [2 5], [5], [4] are almost sorted intervals.

Limbajul de programare folosit: cpp14

Cod:

#ifdef ssu1
#define _GLIBCXX_DEBUG
#endif
#undef NDEBUG

#include <algorithm>
#include <functional>
#include <numeric>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <bitset>
#include <sstream>

using namespace std;

#define fore(i, l, r) for(int i = (l); i < (r); ++i)
#define forn(i, n) fore(i, 0, n)
#define fori(i, l, r) fore(i, l, (r) + 1)
#define sz(v) int((v).size())
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define mp make_pair
#define X first
#define Y second

#if ( _WIN32 || __WIN32__ )
    #define LLD "%I64d"
#else
    #define LLD "%lld"
#endif

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

template<typename T> T abs(T a) { return a < 0 ? -a : a; }
template<typename T> T sqr(T a) { return a*a; }

const int INF = (int)1e9;
const ld EPS = 1e-9;
const ld PI = 3.1415926535897932384626433832795;

int readInt(int l, int r){
    int x;
    if(scanf("%d", &x) != 1){
        fprintf(stderr, "Expected int in range [%d, %d], but haven't found!", l, r);
        throw;
    }
    if(!(l <= x && x <= r)){
        fprintf(stderr, "Expected int in range [%d, %d], but found %d!", l, r, x);
        throw;
    }
    return x;
}

const int NMAX = 1001000;
int t[NMAX], n;
vector<int> rv[NMAX];

inline int sum(int r){
    int ans = 0;
    for(; r >= 0; r = (r & (r + 1)) - 1)
        ans += t[r];
    return ans;
}

inline int sum(int l, int r){
    return sum(r) - sum(l - 1);
}

inline void upd(int i, int dx){
    for(; i < n; i = (i | (i + 1))){
        t[i] += dx;
    }
}

li solve(const vector<int>& a){
    vector<int> lf(sz(a)), rg(sz(a)), st;
    for(int i = sz(a) - 1; i >= 0; --i){
        while(!st.empty() && a[st.back()] >= a[i])
            st.pop_back();
        lf[i] = (st.empty() ? sz(a) : st.back());
        st.pb(i);
    }
    st.clear();
    forn(i, sz(a)){
        while(!st.empty() && a[st.back()] <= a[i])
            st.pop_back();
        rg[i] = (st.empty() ? -1 : st.back());
        st.pb(i);
    }

    forn(i, sz(rg)){
        rv[rg[i] + 1].pb(i);
    }

    li ans = 0;
    forn(i, sz(a)){
        forn(j, sz(rv[i])){
            upd(rv[i][j], 1);
        }
        ans += sum(i, lf[i] - 1);
    }
    return ans;
}

int main(){
#ifdef ssu1
    assert(freopen("input.txt", "rt", stdin));
    //assert(freopen("output.txt", "wt", stdout));
#endif

    n = readInt(1, 1000000);
    vector<int> a(n);
    forn(i, n){
        a[i] = readInt(1, n) - 1;
    }
    cout << solve(a) << endl;
    return 0;
}

Scor obtinut: 1.0

Submission ID: 464655662

Link challenge: https://www.hackerrank.com/challenges/almost-sorted-interval/problem

Almost sorted interval