結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
|
提出日時 | 2020-06-26 21:28:33 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 954 ms / 2,000 ms |
コード長 | 2,809 bytes |
コンパイル時間 | 2,295 ms |
コンパイル使用メモリ | 213,424 KB |
最終ジャッジ日時 | 2025-01-11 10:48:44 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;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.assign(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> A(N);for(int i=0; i<N; i++) cin >> A[i];const int INF = 1e9;int ans = INF;for(int t=0; t<2; t++){map<int, vector<int>> mp;for(int i=0; i<N; i++) mp[(t ? A[i] : -A[i])].push_back(i);Segtree<int> st(N, [](int a, int b){ return min(a, b); }, INF);for(auto& pp : mp){auto& v = pp.second;for(int i : v){int a = st.between(0, i-1), b = st.between(i+1, N-1);if(a < INF && b < INF) ans = min(ans, a+b+A[i]);}for(int i : v) st.update(i, A[i]);}}if(ans == INF) ans = -1;cout << ans << endl;return 0;}