結果
| 問題 |
No.1188 レベルX門松列
|
| コンテスト | |
| ユーザー |
 Ricky_pon
|
| 提出日時 | 2020-08-22 13:57:12 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 118 ms / 2,000 ms |
| コード長 | 5,450 bytes |
| コンパイル時間 | 2,880 ms |
| コンパイル使用メモリ | 202,332 KB |
| 最終ジャッジ日時 | 2025-01-13 08:16:03 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 21 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:157:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
157 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
main.cpp:160:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
160 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>
#define For(i, a, b) for (int(i) = (int)(a); (i) < (int)(b); ++(i))
#define rFor(i, a, b) for (int(i) = (int)(a)-1; (i) >= (int)(b); --(i))
#define rep(i, n) For((i), 0, (n))
#define rrep(i, n) rFor((i), (n), 0)
#define fi first
#define se second
using namespace std;
typedef long long lint;
typedef unsigned long long ulint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
template <class T>
bool chmax(T &a, const T &b) {
if (a < b) {
a = b;
return true;
}
return false;
}
template <class T>
bool chmin(T &a, const T &b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template <class T>
T div_floor(T a, T b) {
if (b < 0) a *= -1, b *= -1;
return a >= 0 ? a / b : (a + 1) / b - 1;
}
template <class T>
T div_ceil(T a, T b) {
if (b < 0) a *= -1, b *= -1;
return a > 0 ? (a - 1) / b + 1 : a / b;
}
constexpr lint mod = 1000000007;
constexpr lint INF = mod * mod;
constexpr int MAX = 200010;
template <typename T, typename E, typename F, typename G>
struct SegTree {
int sz = 1, seq_sz;
T et;
F f;
G g;
vector<T> node;
SegTree(int sz_, T et, F f, G g) : seq_sz(sz_), et(et), f(f), g(g) {
while (sz < sz_) sz <<= 1;
node.resize(sz << 1, et);
}
void build(vector<T> &a) {
rep(i, a.size()) node[i + sz] = a[i];
rFor(i, sz, 1) node[i] = f(node[i << 1], node[(i << 1) + 1]);
}
void build(T x) {
rep(i, seq_sz) node[i + sz] = x;
rFor(i, sz, 1) node[i] = f(node[i << 1], node[(i << 1) + 1]);
}
void update(int i, E x) {
i += sz;
node[i] = g(node[i], x);
i >>= 1;
while (i) {
node[i] = f(node[i << 1], node[(i << 1) + 1]);
i >>= 1;
}
}
T query(int l, int r) {
T vl = et, vr = et;
for (l += sz, r += sz; l < r; l >>= 1, r >>= 1) {
if (l & 1) vl = f(vl, node[l++]);
if (r & 1) vr = f(node[--r], vr);
}
return f(vl, vr);
}
int search_left(int l, const T val, function<bool(T, T)> cmp,
function<bool(T, T)> check) {
T sum = et;
for (l += sz;; l >>= 1) {
if (check(f(sum, node[l]), val)) {
while (l < sz) {
if (check(f(sum, node[l << 1]), val))
l <<= 1;
else {
sum = f(sum, node[l << 1]);
l = (l << 1) + 1;
}
}
return l - sz;
}
if (__builtin_popcount(l + 1) == 1) return seq_sz;
if (l & 1) sum = f(sum, node[l++]);
}
}
int search_right(int r, const T val, function<bool(T, T)> cmp,
function<bool(T, T)> check) {
T sum = et;
for (r += sz;; r >>= 1) {
if (check(f(sum, node[r]), val)) {
while (r < sz) {
if (check(f(node[(r << 1) + 1], sum), val))
r = (r << 1) + 1;
else {
sum = f(node[(r << 1) + 1], sum);
r <<= 1;
}
}
return r - sz;
}
if (__builtin_popcount(r) == 1) return -1;
if (!(r & 1)) sum = f(node[r--], sum);
}
}
int lower_bound_left(int l, const T val,
function<bool(T, T)> cmp = less<>()) {
auto check = [&cmp](auto a, auto b) { return !cmp(a, b); };
return search_left(l, val, cmp, check);
}
int upper_bound_left(int l, const T val,
function<bool(T, T)> cmp = less<>()) {
auto check = [&cmp](auto a, auto b) { return cmp(b, a); };
return search_left(l, val, cmp, check);
}
int lower_bound_right(int l, const T val,
function<bool(T, T)> cmp = greater<>()) {
auto check = [&cmp](auto a, auto b) { return !cmp(b, a); };
return search_right(l, val, cmp, check);
}
int upper_bound_right(int l, const T val,
function<bool(T, T)> cmp = greater<>()) {
auto check = [&cmp](auto a, auto b) { return cmp(a, b); };
return search_right(l, val, cmp, check);
}
};
vector<int> v;
int idx(int x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); }
int main() {
int n;
scanf("%d", &n);
int a[n];
rep(i, n) {
scanf("%d", &a[i]);
v.push_back(a[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
auto f = [](int x, int y) { return max(x, y); };
SegTree<int, int, decltype(f), decltype(f)> st_f1(n, 0, f, f),
st_f2(n, 0, f, f), st_b1(n, 0, f, f), st_b2(n, 0, f, f);
int f1[n], f2[n], b1[n], b2[n];
rep(i, n) {
int pos = idx(a[i]);
f1[i] = st_f1.query(0, pos) + 1;
f2[i] = st_f2.query(pos + 1, n) + 1;
st_f1.update(pos, f1[i]);
st_f2.update(pos, f2[i]);
}
rrep(i, n) {
int pos = idx(a[i]);
b1[i] = st_b1.query(0, pos) + 1;
b2[i] = st_b2.query(pos + 1, n) + 1;
st_b1.update(pos, b1[i]);
st_b2.update(pos, b2[i]);
}
int ans = 0;
rep(i, n) {
chmax(ans, min(f1[i], b1[i]) - 1);
chmax(ans, min(f2[i], b2[i]) - 1);
}
printf("%d\n", ans);
}