結果
問題 | No.1031 いたずら好きなお姉ちゃん |
ユーザー | tsutaj |
提出日時 | 2020-04-22 00:37:00 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,307 ms / 3,500 ms |
コード長 | 4,530 bytes |
コンパイル時間 | 1,844 ms |
コンパイル使用メモリ | 128,844 KB |
実行使用メモリ | 15,000 KB |
最終ジャッジ日時 | 2024-04-17 22:26:45 |
合計ジャッジ時間 | 54,829 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 48 ms
6,944 KB |
testcase_04 | AC | 49 ms
6,940 KB |
testcase_05 | AC | 48 ms
6,940 KB |
testcase_06 | AC | 49 ms
6,940 KB |
testcase_07 | AC | 48 ms
6,940 KB |
testcase_08 | AC | 48 ms
6,944 KB |
testcase_09 | AC | 48 ms
6,940 KB |
testcase_10 | AC | 47 ms
6,944 KB |
testcase_11 | AC | 1,037 ms
13,304 KB |
testcase_12 | AC | 1,041 ms
12,668 KB |
testcase_13 | AC | 1,274 ms
14,308 KB |
testcase_14 | AC | 1,086 ms
13,748 KB |
testcase_15 | AC | 1,219 ms
13,656 KB |
testcase_16 | AC | 1,044 ms
12,788 KB |
testcase_17 | AC | 1,228 ms
13,440 KB |
testcase_18 | AC | 1,181 ms
13,056 KB |
testcase_19 | AC | 1,234 ms
13,448 KB |
testcase_20 | AC | 1,307 ms
13,580 KB |
testcase_21 | AC | 1,167 ms
13,588 KB |
testcase_22 | AC | 1,052 ms
13,832 KB |
testcase_23 | AC | 1,077 ms
13,744 KB |
testcase_24 | AC | 1,216 ms
12,848 KB |
testcase_25 | AC | 1,274 ms
14,784 KB |
testcase_26 | AC | 1,195 ms
13,700 KB |
testcase_27 | AC | 1,094 ms
14,280 KB |
testcase_28 | AC | 1,281 ms
13,824 KB |
testcase_29 | AC | 1,289 ms
14,280 KB |
testcase_30 | AC | 1,290 ms
15,000 KB |
testcase_31 | AC | 1,278 ms
14,976 KB |
testcase_32 | AC | 1,264 ms
14,408 KB |
testcase_33 | AC | 1,255 ms
13,824 KB |
testcase_34 | AC | 1,216 ms
13,272 KB |
testcase_35 | AC | 1,202 ms
13,244 KB |
testcase_36 | AC | 1,197 ms
12,960 KB |
testcase_37 | AC | 1,200 ms
13,376 KB |
testcase_38 | AC | 1,165 ms
12,896 KB |
testcase_39 | AC | 1,127 ms
12,768 KB |
testcase_40 | AC | 1,159 ms
12,976 KB |
testcase_41 | AC | 1,174 ms
12,800 KB |
testcase_42 | AC | 1,154 ms
13,100 KB |
testcase_43 | AC | 1,160 ms
13,176 KB |
testcase_44 | AC | 1,145 ms
13,360 KB |
testcase_45 | AC | 1,137 ms
13,452 KB |
testcase_46 | AC | 1,179 ms
13,180 KB |
testcase_47 | AC | 1,152 ms
13,044 KB |
testcase_48 | AC | 1,188 ms
13,244 KB |
testcase_49 | AC | 1,207 ms
13,072 KB |
testcase_50 | AC | 1,155 ms
13,140 KB |
testcase_51 | AC | 1,189 ms
13,056 KB |
testcase_52 | AC | 1,192 ms
13,056 KB |
testcase_53 | AC | 1,183 ms
13,092 KB |
testcase_54 | AC | 2 ms
6,940 KB |
testcase_55 | AC | 2 ms
6,940 KB |
ソースコード
// #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; }