結果
問題 | No.956 Number of Unbalanced |
ユーザー |
![]() |
提出日時 | 2019-12-20 23:42:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 52 ms / 2,000 ms |
コード長 | 1,045 bytes |
コンパイル時間 | 480 ms |
コンパイル使用メモリ | 56,904 KB |
実行使用メモリ | 7,680 KB |
最終ジャッジ日時 | 2024-07-18 03:14:11 |
合計ジャッジ時間 | 2,332 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 24 |
ソースコード
#include <cstdio> #include <algorithm> #include <vector> using namespace std; namespace{ typedef long long LL; void main2(){ int n; scanf("%d", &n); vector<int> as(n); for(int i = 0; i < n; ++i){ scanf("%d", &as[i]); } int mval = *max_element(as.begin(), as.end()); vector<vector<int> > postbl(mval + 1); for(int i = 0; i < n; ++i){ postbl[as[i]].push_back(i); } vector<int> cnts; cnts.reserve(2 * n + 10); LL ans = 0; for(int x = 0; x <= mval; ++x){ const vector<int> &poss = postbl[x]; int sz = poss.size(); for(int l = 0; l < sz; ){ int r; for(r = l + 1; r < sz && poss[r] - poss[r - 1] <= sz; ++r); int beg = max(poss[l] - (r - l) + 1, 0); int en = min(poss[r - 1] + (r - l), n); cnts.assign((en - beg) * 2 + 8, 0); int h = en - beg + 4; cnts[h] = 1; LL low = 0; for(int i = beg; i < en; ++i){ if(x == as[i]){ low += cnts[h++]; } else{ low -= cnts[--h]; } ++cnts[h]; ans += low; } l = r; } } printf("%lld\n", ans); } } int main(){ main2(); }