Untitled
#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