結果
問題 | No.1031 いたずら好きなお姉ちゃん |
ユーザー |
|
提出日時 | 2020-04-17 23:19:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 198 ms / 3,500 ms |
コード長 | 3,853 bytes |
コンパイル時間 | 2,783 ms |
コンパイル使用メモリ | 209,280 KB |
最終ジャッジ日時 | 2025-01-09 20:45:26 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 53 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T> struct BIT { int n; vector<T> dat; BIT(int n=0){ initialize(n); } void initialize(int nin){ n = nin; dat.resize(n, 0); } T sum(int i){ T s = 0; while(i >= 0){ s += dat[i]; i = (i & (i+1)) - 1; } return s; } T sum_between(int i, int j){ return sum(j) - sum(i-1); } void plus(int i, T x){ while(i < n){ dat[i] += x; i |= i+1; } } // a[0]+...+a[ret] >= x int lower_bound(T x){ if(x < 0) return -1; int ret = -1; int k = 1; while(2*k <= n) k <<= 1; for( ;k>0; k>>=1){ if(ret+k < n && dat[ret+k] < x){ x -= dat[ret+k]; ret += k; } } return ret + 1; } }; template<typename T> struct Segtree { int n, n_org; T e; vector<T> dat; typedef function<T(T a, T b)> Func; Func f; Segtree(){} Segtree(int n_input, Func f_input, T e_input){ initialize(n_input, f_input, e_input); } void initialize(int n_input, Func f_input, T e_input){ n_org = n_input; f = f_input; e = e_input; n = 1; while(n < n_input) n <<= 1; dat.resize(2*n-1, e); } void build(vector<T>& A){ for(int k=0; k<int(A.size()); k++) dat[k+n-1] = A[k]; for(int k=n-2; k>=0; k--) dat[k] = f(dat[2*k+1], dat[2*k+2]); } void update(int k, T a){ k += n - 1; dat[k] = a; while(k > 0){ k = (k - 1)/2; dat[k] = f(dat[2*k+1], dat[2*k+2]); } } T get(int k){ return dat[k+n-1]; } T between(int a, int b){ return query(a, b+1, 0, 0, n); } T query(int a, int b, int k, int l, int r){ if(r<=a || b<=l) return e; if(a<=l && r<=b) return dat[k]; T vl = query(a, b, 2*k+1, l, (l+r)/2); T vr = query(a, b, 2*k+2, (l+r)/2, r); return f(vl, vr); } // [S, t] が条件checkを満たす最大のtを求める int bisect(int S, function<bool(T a)> check){ T val = get(S); int k = S+n-1, l = S, r = S+1; while(true){ while(k%2) k = (k-1)/2, r += r-l; T val2 = f(val, dat[k]); if(check(val2)){ if(r == n) return n_org-1; val = val2; k++; int d = r-l; l += d, r += d; }else{ break; } } while(k<n-1){ T val2 = f(val, dat[2*k+1]); if(check(val2)){ val = val2; k = 2*k+2; l = (l+r)/2; }else{ k = 2*k+1; r = (l+r)/2; } } return min(l, n_org)-1; } }; int main(){ int N; cin >> N; vector<int> P(N); for(int i=0; i<N; i++) cin >> P[i], P[i]--; int64_t ans = 0; for(int t=0; t<2; t++){ priority_queue<pair<int, int>> que; vector<vector<int>> out(N); for(int i=0; i<N; i++){ while(que.size() && que.top().first > P[i]){ out[i].push_back(que.top().second); que.pop(); } que.emplace(P[i], i); } BIT<int> bit(N); Segtree<int> st(N, [](int a, int b){ return max(a, b); }, -1); for(int i=0; i<N; i++){ int L = st.between(P[i]+1, N-1) + 1; ans += bit.sum_between(L, i); bit.plus(i, 1); for(int a : out[i]) bit.plus(a, -1); st.update(P[i], i); } reverse(P.begin(), P.end()); } cout << ans << endl; return 0; }