C11PAIRS - Đếm cặp
Tác giả: flashmt
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int n,st[500500],cnt[500500],last;
long long ans;
int main()
{
int x;
cin >> n;
for (int i=1;i<=n;i++)
{
scanf("%d",&x);
int j=0,same=0;
while (last && st[last]<=x)
{
j+=cnt[last];
if (st[last]==x) same=1;
last--;
}
if (st[last]>x) j++;
if (i>1) ans+=j;
if (!same) st[++last]=x, cnt[last]=1;
else cnt[++last]++;
}
cout << ans << endl;
}