C11PAIRS - Đếm cặp

Tác giả: skyvn97

Ngôn ngữ: C++

#include<bits/stdc++.h>
#define MAX   500500
#define v   first
#define e   second
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
int a[MAX];
int n;
ll res;
stack<ii> st;
void init(void) {
    scanf("%d",&n);
    int i;
    for (i=1;i<=n;i=i+1) scanf("%d",&a[i]);
}
void process(void) {
    while (!st.empty()) st.pop();
    res=0LL;
    int i;
    for (i=1;i<=n;i=i+1) {
        if (st.empty()) st.push(ii(a[i],1));
        else {
            if (st.top().v>a[i]) {
                res++;
                st.push(ii(a[i],1));
            }
            else if (st.top().v==a[i]) {
                res+=st.top().e+(st.size()>1);
                st.top().e++;
            }
            else {
                while (!st.empty() && st.top().v<a[i]) {
                    res+=st.top().e;
                    st.pop();
                }
                if (st.empty()) st.push(ii(a[i],1));
                else {
                    if (st.top().v==a[i]) {
                        res+=st.top().e+(st.size()>1);
                        st.top().e++;
                    }
                    else {
                        res++;
                        st.push(ii(a[i],1));
                    }
                }
            }
        }
    }
    printf("%lld",res);
}
int main(void) {
    init();
    process();
    return 0;
}

Download