結果
問題 |
No.1031 いたずら好きなお姉ちゃん
|
ユーザー |
![]() |
提出日時 | 2020-04-22 00:37:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,339 ms / 3,500 ms |
コード長 | 4,530 bytes |
コンパイル時間 | 1,806 ms |
コンパイル使用メモリ | 130,212 KB |
実行使用メモリ | 14,976 KB |
最終ジャッジ日時 | 2024-10-09 16:10:06 |
合計ジャッジ時間 | 56,671 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
// #define _GLIBCXX_DEBUG // for STL debug (optional) #include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <cfloat> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <fstream> #include <functional> #include <bitset> using namespace std; using ll = long long int; using int64 = long long int; template<typename T> void chmax(T &a, T b) {a = max(a, b);} template<typename T> void chmin(T &a, T b) {a = min(a, b);} template<typename T> void chadd(T &a, T b) {a = a + b;} int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const int INF = 1LL << 29; const ll LONGINF = 1LL << 60; const ll MOD = 1000000007LL; // @category セグメント木 (Segment Tree) // @title セグメント木 (Segment Tree) // 抽象 SegmentTree (0-indexed・一点更新・区間取得) template <typename MonoidType> struct SegmentTree { using Function = function< MonoidType(MonoidType, MonoidType) >; // node, identity element int n; vector<MonoidType> node; MonoidType E0; // update / combine function Function upd_f, cmb_f; void build(int m, vector<MonoidType> v = vector<MonoidType>()) { if(v != vector<MonoidType>()) m = v.size(); n = 1; while(n < m) n *= 2; node = vector<MonoidType>(2*n-1, E0); if(v != vector<MonoidType>()) { for(int i=0; i<m; i++) { node[n-1+i] = v[i]; } for(int i=n-2; i>=0; i--) { node[i] = cmb_f(node[2*i+1], node[2*i+2]); } } } // initialize SegmentTree() {} SegmentTree(int n_, MonoidType E0_, Function upd_f_, Function cmb_f_, vector<MonoidType> v = vector<MonoidType>()) : E0(E0_), upd_f(upd_f_), cmb_f(cmb_f_) { build(n_, v); } // update k-th element (applied value: x) void update(int k, MonoidType x) { k += n - 1; node[k] = upd_f(node[k], x); while(k > 0) { k = (k - 1) / 2; node[k] = cmb_f(node[2*k+1], node[2*k+2]); } } // range query for [a, b) // 非再帰のアイデア: http://d.hatena.ne.jp/komiyam/20131202/1385992406 MonoidType query(int a, int b) { MonoidType vl = E0, vr = E0; for(int l=a+n, r=b+n; l<r; l>>=1, r>>=1) { if(l & 1) vl = cmb_f(vl, node[(l++)-1]); if(r & 1) vr = cmb_f(node[(--r)-1], vr); } return cmb_f(vl, vr); } }; ll solve(const vector<int> &A) { int N = A.size(); SegmentTree<int> seg(N, 0, [](int a, int b) { return a + b; }, [](int a, int b) { return a + b; }); vector<int> L(N), R(N), ord(N); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&A](int x, int y) { return A[x] < A[y]; }); // min { set<int> S; for(int i=0; i<N; i++) { int k = ord[i]; auto ptr = S.lower_bound(k); if(ptr == S.end()) R[k] = N; else R[k] = *ptr; S.emplace(k); } } reverse(ord.begin(), ord.end()); // max { set<int> S; for(int i=0; i<N; i++) { int k = ord[i]; auto ptr = S.lower_bound(k); if(ptr == S.begin()) L[k] = -1; else L[k] = *prev(ptr); S.emplace(k); } } fprintf(stderr, "L:"); for(auto e : L) cerr << " " << e; cerr << endl; fprintf(stderr, "R:"); for(auto e : R) cerr << " " << e; cerr << endl; vector< tuple<int, int, int> > rec; for(int i=0; i<N; i++) { rec.emplace_back(i, 1, i); // min (query) rec.emplace_back(L[i], 2, i); // max (add) } sort(rec.begin(), rec.end()); ll res = -N; for(int i=0; i<2*N; i++) { int v, t, k; tie(v, t, k) = rec[i]; if(t == 1) { int a = seg.query(k, R[k]); res += a; } if(t == 2) { seg.update(k, +1); } } return res; } int main() { int N; scanf("%d", &N); vector<int> A(N); for(int i=0; i<N; i++) scanf("%d", &A[i]); ll ans = 0; ans += solve(A); reverse(A.begin(), A.end()); ans += solve(A); printf("%lld\n", ans); return 0; }