結果
問題 | No.992 最長増加部分列の数え上げ |
ユーザー | jell |
提出日時 | 2020-04-06 22:43:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 194 ms / 2,000 ms |
コード長 | 12,570 bytes |
コンパイル時間 | 1,319 ms |
コンパイル使用メモリ | 112,796 KB |
実行使用メモリ | 11,904 KB |
最終ジャッジ日時 | 2024-07-07 03:49:24 |
合計ジャッジ時間 | 9,758 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 68 ms
7,040 KB |
testcase_05 | AC | 49 ms
5,504 KB |
testcase_06 | AC | 84 ms
7,424 KB |
testcase_07 | AC | 89 ms
7,040 KB |
testcase_08 | AC | 31 ms
6,940 KB |
testcase_09 | AC | 61 ms
6,944 KB |
testcase_10 | AC | 82 ms
7,424 KB |
testcase_11 | AC | 104 ms
8,064 KB |
testcase_12 | AC | 22 ms
5,376 KB |
testcase_13 | AC | 59 ms
6,912 KB |
testcase_14 | AC | 59 ms
6,912 KB |
testcase_15 | AC | 21 ms
5,376 KB |
testcase_16 | AC | 161 ms
11,392 KB |
testcase_17 | AC | 32 ms
5,376 KB |
testcase_18 | AC | 56 ms
6,784 KB |
testcase_19 | AC | 101 ms
7,808 KB |
testcase_20 | AC | 177 ms
11,776 KB |
testcase_21 | AC | 180 ms
11,688 KB |
testcase_22 | AC | 179 ms
11,720 KB |
testcase_23 | AC | 177 ms
11,776 KB |
testcase_24 | AC | 178 ms
11,776 KB |
testcase_25 | AC | 174 ms
11,776 KB |
testcase_26 | AC | 188 ms
11,648 KB |
testcase_27 | AC | 194 ms
11,776 KB |
testcase_28 | AC | 180 ms
11,904 KB |
testcase_29 | AC | 182 ms
11,776 KB |
testcase_30 | AC | 147 ms
11,648 KB |
testcase_31 | AC | 151 ms
11,648 KB |
testcase_32 | AC | 152 ms
11,648 KB |
testcase_33 | AC | 146 ms
11,636 KB |
testcase_34 | AC | 143 ms
11,680 KB |
testcase_35 | AC | 145 ms
11,648 KB |
testcase_36 | AC | 147 ms
11,648 KB |
testcase_37 | AC | 146 ms
11,740 KB |
testcase_38 | AC | 150 ms
11,648 KB |
testcase_39 | AC | 147 ms
11,648 KB |
testcase_40 | AC | 144 ms
11,648 KB |
testcase_41 | AC | 143 ms
11,648 KB |
testcase_42 | AC | 140 ms
11,648 KB |
testcase_43 | AC | 145 ms
11,672 KB |
testcase_44 | AC | 149 ms
11,648 KB |
コンパイルメッセージ
main.cpp:318:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 318 | main() | ^~~~
ソースコード
#include <iostream> #include <vector> #include <bitset> #include <functional> #include <queue> #include <algorithm> #include <map> #include <set> #include <tuple> #include <numeric> using namespace std; #ifndef Modint_hpp #define Modint_hpp #include <cassert> #include <iostream> template <int mod> class modint { int val; public: constexpr modint() noexcept : val{0} {} constexpr modint(long long x) noexcept : val((x %= mod) < 0 ? mod + x : x) {} constexpr long long value() const noexcept { return val; } constexpr modint operator++(int) noexcept { modint t = *this; return ++val, t; } constexpr modint operator--(int) noexcept { modint t = *this; return --val, t; } constexpr modint &operator++() noexcept { return ++val, *this; } constexpr modint &operator--() noexcept { return --val, *this; } constexpr modint operator-() const noexcept { return modint(-val); } constexpr modint &operator+=(const modint &other) noexcept { return (val += other.val) < mod ? 0 : val -= mod, *this; } constexpr modint &operator-=(const modint &other) noexcept { return (val += mod - other.val) < mod ? 0 : val -= mod, *this; } constexpr modint &operator*=(const modint &other) noexcept { return val = (long long)val * other.val % mod, *this; } constexpr modint &operator/=(const modint &other) noexcept { return *this *= inverse(other); } constexpr modint operator+(const modint &other) const noexcept { return modint(*this) += other; } constexpr modint operator-(const modint &other) const noexcept { return modint(*this) -= other; } constexpr modint operator*(const modint &other) const noexcept { return modint(*this) *= other; } constexpr modint operator/(const modint &other) const noexcept { return modint(*this) /= other; } constexpr bool operator==(const modint &other) const noexcept { return val == other.val; } constexpr bool operator!=(const modint &other) const noexcept { return val != other.val; } constexpr bool operator!() const noexcept { return !val; } friend constexpr modint operator+(long long x, modint y) noexcept { return modint(x) + y; } friend constexpr modint operator-(long long x, modint y) noexcept { return modint(x) - y; } friend constexpr modint operator*(long long x, modint y) noexcept { return modint(x) * y; } friend constexpr modint operator/(long long x, modint y) noexcept { return modint(x) / y; } static constexpr modint inverse(const modint &other) noexcept { assert(other != 0); int a{mod}, b{other.val}, u{}, v{1}, t{}; while(b) t = a / b, a ^= b ^= (a -= t * b) ^= b, u ^= v ^= (u -= t * v) ^= v; return {u}; } static constexpr modint pow(modint other, long long e) noexcept { if(e < 0) e = e % (mod - 1) + mod - 1; modint res{1}; while(e) { if(e & 1) res *= other; other *= other, e >>= 1; } return res; } friend std::ostream &operator<<(std::ostream &os, const modint &other) noexcept { return os << other.val; } friend std::istream &operator>>(std::istream &is, modint &other) noexcept { long long val; other = {(is >> val, val)}; return is; } }; // class modint template <> class modint<2> { bool val; public: constexpr modint(bool x = false) noexcept : val{x} {} constexpr modint(int x) noexcept : val(x & 1) {} constexpr modint(long long x) noexcept : val(x & 1) {} constexpr operator bool() const noexcept { return val; } constexpr bool value() const noexcept { return val; } constexpr modint &operator+=(const modint &other) noexcept { return val ^= other.val, *this; } constexpr modint &operator-=(const modint &other) noexcept { return val ^= other.val, *this; } constexpr modint &operator*=(const modint &other) noexcept { return val &= other.val, *this; } constexpr modint &operator/=(const modint &other) noexcept { assert(other.val); return *this; } constexpr modint operator!() const noexcept { return !val; } constexpr modint operator-() const noexcept { return *this; } constexpr modint operator+(const modint &other) const noexcept { return val != other.val; } constexpr modint operator-(const modint &other) const noexcept { return val != other.val; } constexpr modint operator*(const modint &other) const noexcept { return val && other.val; } constexpr modint operator/(const modint &other) const noexcept { assert(other.val); return *this; } constexpr bool operator==(const modint &other) const noexcept { return val == other.val; } constexpr bool operator!=(const modint &other) const noexcept { return val != other.val; } friend constexpr modint operator+(long long x, modint y) noexcept { return x & 1 ? !y : y; } friend constexpr modint operator-(long long x, modint y) noexcept { return x & 1 ? !y : y; } friend constexpr modint operator*(long long x, modint y) noexcept { return x & 1 ? y : modint<2>{0}; } friend constexpr modint operator/(long long x, modint y) noexcept { assert(y.val); return x & 1 ? y : modint<2>{0}; } friend std::ostream &operator<<(std::ostream &os, const modint &other) noexcept { return os << other.val; } friend std::istream &operator>>(std::istream &is, modint &other) noexcept { long long val; other.val = (is >> val, val & 1); return is; } }; // class modint specialization #endif // Modint_hpp template <class T> struct coordinate_compression { std::vector<T> raw, uniquely; std::vector<size_t> compressed; coordinate_compression(std::vector<T> &_raw) : raw(_raw), compressed(_raw.size()) { std::sort(_raw.begin(), _raw.end()); _raw.erase(std::unique(_raw.begin(), _raw.end()), _raw.end()); uniquely = _raw; for(size_t i = 0; i != raw.size(); ++i) { compressed[i] = std::lower_bound(_raw.begin(), _raw.end(), raw[i]) - _raw.begin(); } } size_t operator[](const size_t idx) const { assert(idx < compressed.size()); return compressed[idx]; } size_t kind() const { return uniquely.size(); } T restore(const size_t ord) const { assert(ord < uniquely.size()); return uniquely[ord]; } size_t order_of(const T &val) const { return std::lower_bound(uniquely.begin(), uniquely.end(), val) - uniquely.begin(); } }; #include <cassert> #include <vector> template <class monoid> class segment_tree { using size_type = typename std::vector<monoid>::size_type; class unique_queue { size_type *que, *begin, *end; bool *in; public: unique_queue() : que(), begin(), end(), in() {} unique_queue(size_type n) : que(new size_type[n]), begin(que), end(que), in(new bool[n]{}) {} ~unique_queue() { delete[] que; delete[] in; } void clear() { begin = end = que; } bool empty() const { return begin == end; } bool push(size_type index) { if(in[index]) return false; return in[*end++ = index] = true; } size_type pop() { return in[*begin] = false, *begin++; } }; // struct unique_queue size_type size_orig, height, size_ext; std::vector<monoid> data; unique_queue que; void recalc(const size_type node) { data[node] = data[node << 1] + data[node << 1 | 1]; } void rebuild() { while(!que.empty()) { const size_type index = que.pop() >> 1; if(index && que.push(index)) recalc(index); } que.clear(); } template <class pred_type> size_type left_search_subtree(size_type index, const pred_type pred, monoid mono) const { assert(index); while(index < size_ext) { const monoid tmp = data[(index <<= 1) | 1] + mono; if(pred(tmp)) mono = tmp; else ++index; } return ++index -= size_ext; } template <class pred_type> size_type right_search_subtree(size_type index, const pred_type pred, monoid mono) const { assert(index); while(index < size_ext) { const monoid tmp = mono + data[index <<= 1]; if(pred(tmp)) ++index, mono = tmp; } return (index -= size_ext) < size_orig ? index : size_orig; } public: segment_tree(const size_type n = 0) : size_orig{n}, height(n > 1 ? 32 - __builtin_clz(n - 1) : 0), size_ext{1u << height}, data(size_ext << 1), que(size_ext << 1) {} segment_tree(const size_type n, const monoid &init) : segment_tree(n) { std::fill(std::next(std::begin(data), size_ext), std::end(data), init); for(size_type i{size_ext}; --i; ) recalc(i); } template <class iter_type, class value_type = typename std::iterator_traits<iter_type>::value_type> segment_tree(iter_type first, iter_type last) : size_orig(std::distance(first, last)), height(size_orig > 1 ? 32 - __builtin_clz(size_orig - 1) : 0), size_ext{1u << height}, data(size_ext << 1), que(size_ext << 1) { static_assert(std::is_constructible<monoid, value_type>::value, "monoid(iter_type::value_type) is not constructible."); for(auto iter{std::next(std::begin(data), size_ext)}; iter != std::end(data) && first != last; ++iter, ++first) *iter = monoid{*first}; for(size_type i{size_ext}; --i; ) recalc(i); } template <class container_type, typename = typename container_type::value_type> segment_tree(const container_type &cont) : segment_tree(std::begin(cont), std::end(cont)) {} size_type size() const { return size_orig; } size_type capacity() const { return size_ext; } // reference to the element at the index. typename decltype(data)::reference operator[](size_type index) { assert(index < size_orig); que.push(index |= size_ext); return data[index]; } // const reference to the element at the index. typename decltype(data)::const_reference operator[](size_type index) const { assert(index < size_orig); return data[index |= size_orig]; } monoid fold(size_type first, size_type last) { assert(last <= size_orig); rebuild(); monoid leftval{}, rightval{}; first += size_ext, last += size_ext; while(first < last) { if(first & 1) leftval = leftval + data[first++]; if(last & 1) rightval = data[--last] + rightval; first >>= 1, last >>= 1; } return leftval + rightval; } monoid fold() { return fold(0, size_orig); } template <class pred_type> size_type left_search(size_type right, const pred_type pred) { assert(right <= size_orig); rebuild(); right += size_ext; monoid mono{}; for(size_type left{size_ext}; left != right; left >>= 1, right >>= 1) { if((left & 1) != (right & 1)) { const monoid tmp = data[--right] + mono; if(!pred(tmp)) return left_search_subtree(right, pred, mono); mono = tmp; } } return 0; } template <class pred_type> size_type right_search(size_type left, const pred_type pred) { assert(left <= size_orig); rebuild(); left += size_ext; monoid mono{}; for(size_type right{size_ext << 1}; left != right; left >>= 1, right >>= 1) { if((left & 1) != (right & 1)) { const monoid tmp = mono + data[left]; if(!pred(tmp)) return right_search_subtree(left, pred, mono); mono = tmp; ++left; } } return size_orig; } }; // class segment_tree using mint=modint<int(1e9+7)>; struct mono_type { int val; mint cnt; mono_type(int v=0,int c=0) : val(v),cnt(c) {} // binary operation mono_type operator+(const mono_type& rhs) const { return mono_type{*this} += rhs; } // operation assignment mono_type &operator+=(const mono_type &rhs) { if(val<rhs.val) *this=rhs; else if(val==rhs.val) cnt+=rhs.cnt; return *this; } }; main() { int n; cin>>n; vector<int> a(n); for(int &e :a) cin>>e; coordinate_compression<int> comp(a); segment_tree<mono_type> seg(n+1, mono_type{0,0}); seg[0].cnt++; for(int i=0;i<n;++i) { int e=comp[i]+1; auto f=seg.fold(0,e); f.val++; seg[e]+=f; } cout << seg.fold().cnt << "\n"; }