結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
![]() |
提出日時 | 2020-08-05 04:35:51 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,788 bytes |
コンパイル時間 | 3,393 ms |
コンパイル使用メモリ | 201,384 KB |
最終ジャッジ日時 | 2025-01-12 14:38:49 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 30 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:75:15: warning: overflow in conversion from ‘long int’ to ‘int’ changes value from ‘10010010001’ to ‘1420075409’ [-Woverflow] 75 | int INF = 10010010001; | ^~~~~~~~~~~
ソースコード
#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_MAX if (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 = 10010010001; 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]); } if(mi == INF) mi = -1; cout << mi << endl; return 0; }