結果
問題 | No.1188 レベルX門松列 |
ユーザー |
|
提出日時 | 2020-08-22 14:42:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 180 ms / 2,000 ms |
コード長 | 3,438 bytes |
コンパイル時間 | 2,649 ms |
コンパイル使用メモリ | 205,664 KB |
最終ジャッジ日時 | 2025-01-13 08:50:43 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> #ifdef DEBUG #include <Mylib/Debug/debug.cpp> #else #define dump(...) #endif /** * @title Segment tree * @docs segment_tree.md */ template <typename Monoid> class SegmentTree{ using value_type = typename Monoid::value_type; Monoid M; int depth, size, hsize; std::vector<value_type> data; public: SegmentTree(){} SegmentTree(int n): depth(n > 1 ? 32-__builtin_clz(n-1) + 1 : 1), size(1 << depth), hsize(size / 2), data(size, M.id()) {} auto operator[](int i) const {return at(i);} auto at(int i) const {return data[hsize + i];} auto get(int x, int y) const { // [x,y) value_type ret_left = M.id(); value_type ret_right = M.id(); int l = x + hsize, r = y + hsize; while(l < r){ if(r & 1) ret_right = M.op(data[--r], ret_right); if(l & 1) ret_left = M.op(ret_left, data[l++]); l >>= 1, r >>= 1; } return M.op(ret_left, ret_right); } void update(int i, const value_type &x){ i += hsize; data[i] = x; while(i > 1) i >>= 1, data[i] = M.op(data[i << 1 | 0], data[i << 1 | 1]); } template <typename T> void init_with_vector(const std::vector<T> &val){ data.assign(size, M.id()); for(int i = 0; i < (int)val.size(); ++i) data[hsize + i] = val[i]; for(int i = hsize-1; i >= 1; --i) data[i] = M.op(data[i << 1 | 0], data[i << 1 | 1]); } template <typename T> void init(const T &val){ init_with_vector(std::vector<value_type>(hsize, val)); } }; /** * @docs max.md */ template <typename T> struct MaxMonoid{ using value_type = std::optional<T>; value_type id() const {return {};} value_type op(const value_type &a, const value_type &b) const { if(not a) return b; if(not b) return a; return {std::max(*a, *b)}; } }; namespace solver{ void compress(std::vector<int> &A){ std::vector<int> B(A); std::sort(B.begin(), B.end()); B.erase(std::unique(B.begin(), B.end()), B.end()); for(auto &x : A){ x = std::lower_bound(B.begin(), B.end(), x) - B.begin(); } } std::vector<int> sub(std::vector<int> A){ const int N = A.size(); SegmentTree<MaxMonoid<int>> seg(N); std::vector<int> ret(N); for(int i = 0; i < N; ++i){ ret[i] = seg.get(A[i] + 1, N).value_or(0) + 1; int t = seg.at(A[i]).value_or(0); seg.update(A[i], std::max(t, ret[i])); } return ret; } void solve(){ std::cin.tie(0); std::ios::sync_with_stdio(false); int N; std::cin >> N; std::vector<int> A(N); for(int i = 0; i < N; ++i) std::cin >> A[i]; int ans = 0; compress(A); { auto res1 = sub(A); std::reverse(A.begin(), A.end()); auto res2 = sub(A); std::reverse(A.begin(), A.end()); std::reverse(res2.begin(), res2.end()); //dump(res1, res2); for(int i = 0; i < N; ++i){ ans = std::max(ans, std::min(res1[i], res2[i]) - 1); } } for(int i = 0; i < N; ++i) A[i] = -A[i]; compress(A); { auto res1 = sub(A); std::reverse(A.begin(), A.end()); auto res2 = sub(A); std::reverse(A.begin(), A.end()); std::reverse(res2.begin(), res2.end()); //dump(res1, res2); for(int i = 0; i < N; ++i){ ans = std::max(ans, std::min(res1[i], res2[i]) - 1); } } std::cout << ans << "\n"; } } int main(){ solver::solve(); return 0; }