結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
![]() |
提出日時 | 2020-08-05 04:43:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 884 ms / 2,000 ms |
コード長 | 3,061 bytes |
コンパイル時間 | 3,853 ms |
コンパイル使用メモリ | 202,396 KB |
最終ジャッジ日時 | 2025-01-12 14:39:11 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>#define rep(i,n) for(int i = 0; i < (n); ++i)#define rrep(i,n) for(int i = 1; i <= (n); ++i)#define drep(i,n) for(int i = (n)-1; i >= 0; --i)#define srep(i,s,t) for (int i = s; i < t; ++i)using namespace std;typedef pair<int,int> P;typedef long long int ll;#define dame { puts("-1"); return 0;}#define yn {puts("Yes");}else{puts("No");}const int MAX_N = 1 << 19;// セグメント木を持つグローバル配列int nn, dat[2 * MAX_N - 1];// 初期化void init(int n_){// n_が小さいときの変な挙動を防ぐif(n_ < 10)n_ = 10;// 簡単のため要素数を2のべき乗にnn = 1;while(nn < n_)nn *= 2;// 全ての値をINT_MAXにfor(int i = 0; i < 2 * nn - 1; i++)dat[i] = INT_MAX;}// k番目の値(0-indexed)をaに変更void update(int k, int a){// 葉の接点k += nn - 1;dat[k] = a;// 登りながら更新while(k > 0){k = (k - 1) / 2;dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);}}// [a,b)の最小値を求める// 後ろのほうの引数は、計算の簡単のための引数。// kは節点の番号、l, rはその節点が[l, r)に対応づいていることを表す。// したがって、外からはquery(a, b, 0, 0, nn)として呼ぶ。int query(int a, int b, int k, int l, int r){// [a, b)と[l, r)が交差しなければ、INT_MAXif (r <= a || b <= l)return INT_MAX;// [a, b)が[l, r)を完全に含んでいれば、この節点の値if (a <= l && r <= b)return dat[k];else {// そうでなければ、2つの子の最小値int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);return min(vl, vr);}}int main(){int n;cin >> n;init(n);int a[n], b[n];map<int,int> mp;rep(i,n){cin >> a[i];b[i] = a[i];mp[a[i]] = i;}sort(b,b+n);int ma = 0;int INF = 1001001001;int mi = INF;rep(i,n){int ite = mp[b[i]];if(ite != 0 && ite != n-1){int l = -query(0,ite,0,0,nn);int r = -query(ite+1,nn,0,0,nn);if(l>-INF && r>-INF){mi = min(mi, l+b[i]+r);ma = max(ma, l+b[i]+r);}}update(ite,-b[i]);}init(n);drep(i,n){int ite = mp[b[i]];if(ite != 0 && ite != n-1){int l = query(0,ite,0,0,nn);int r = query(ite+1,nn,0,0,nn);if(l<INF && r<INF){mi = min(mi, l+b[i]+r);ma = max(ma, l+b[i]+r);}}update(ite,b[i]);}int mil[n], mir[n];mil[0] = INF;srep(i,1,n) mil[i] = min(mil[i-1],a[i-1]);mir[n-1] = INF;drep(i,n-1) mir[i] = min(mir[i+1],a[i+1]);srep(i,1,n-1){if(mil[i]>a[i]||mir[i]>a[i]) continue;mi = min(mi, mil[i]+a[i]+mir[i]);}if(mi == INF) mi = -1;cout << mi << endl;return 0;}