結果
問題 |
No.1031 いたずら好きなお姉ちゃん
|
ユーザー |
![]() |
提出日時 | 2020-04-23 01:56:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 3,500 ms |
コード長 | 947 bytes |
コンパイル時間 | 2,282 ms |
コンパイル使用メモリ | 195,896 KB |
最終ジャッジ日時 | 2025-01-09 22:44:02 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a; a.resize(n); for(int &i : a) { cin >> i; --i; } vector<int> pos; pos.resize(n); for(int i = 0; i < n; ++i) { pos[a[i]] = i; } long long ans = 0; vector<int> st; vector<int> small; for(int i = 0; i < n; ++i) { while(!st.empty() && a[i] > a[st.back()]) { st.pop_back(); } while(!small.empty() && a[i] < a[small.back()]) { small.pop_back(); } if(st.empty()) { ans += small.size(); } else { int p = upper_bound(small.begin(), small.end(), st.back()) - small.begin(); ans += (int)small.size() - p; } if(small.empty()) { ans += st.size(); } else { int p = upper_bound(st.begin(), st.end(), small.back()) - st.begin(); ans += (int)st.size() - p; } small.emplace_back(i); st.emplace_back(i); } cout << ans << '\n'; return 0; }