Untitled

 avatar
unknown
plain_text
20 days ago
2.3 kB
1
Indexable
#include <bits/stdc++.h>

using namespace std;

#define Chris "test"
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORD(i, a, b) for(int i = (a); i <= (b); ++i)
#define REP(i, a, b) for(int i = (a); i > (b); --i)
#define REPD(i, a, b) for(int i = (a); i >= (b); --i)
#define FORE(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define All(v) (v).begin(), (v).end()
#define rAll(v) (v).rbegin(), (v).rend()
#define MARK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
#define MIN(v) *min_element(All(v))
#define MAX(v) *max_element(All(v))
#define el "\n"
#define Chris_ signed main()
#define faster ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define file(Chris) if(fopen(Chris".inp", "r")){freopen(Chris".inp", "r", stdin);freopen(Chris".out", "w", stdout);}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vii;
typedef set<int> sii;
typedef map<int, int> mii;
typedef stack<int> sti;
typedef deque<int> dqi;
typedef queue<int> quei;
typedef unordered_map<int, int> umii;
typedef unordered_set<int, int> umsii;

const int mod = (int) 1e9 + 7;
const int INF = (int) 1e5;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n;
ll ans = 0;



void tinh1()
{

}

void solve()
{
    cin >> n;
    vii a(n), l(n), r(n);
    FOR(i, 0, n) cin >> a[i];
    sti st;
    FOR(i, 0, n)
    {
        while(!st.empty() && a[st.top()] < a[i])
        {
            st.pop();
        }
        l[i] = (st.empty() ? 0 : st.top() + 1);
        st.push(i);
    }
    st = sti();
    REPD(i, n - 1, 0)
    {
        while(!st.empty() && a[st.top()] < a[i])
        {
            st.pop();
        }
        r[i] = (st.empty() ? n - 1 : st.top() - 1);
        st.push(i);
    }
    FOR(i, 0, n)
    {
        ans += r[i] - l[i];
    }
    cout << ans;
}

Chris_
{
    faster
    file(Chris)

    solve();

    cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";

    return 0;
}
Leave a Comment