結果
| 問題 | No.1188 レベルX門松列 |
| ユーザー |
 Ricky_pon
|
| 提出日時 | 2020-08-22 13:51:27 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 5,453 bytes |
| コンパイル時間 | 2,147 ms |
| コンパイル使用メモリ | 210,308 KB |
| 実行使用メモリ | 9,944 KB |
| 最終ジャッジ日時 | 2024-10-15 08:05:56 |
| 合計ジャッジ時間 | 3,999 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge5 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 41 ms
9,932 KB |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | AC | 40 ms
9,940 KB |
| testcase_07 | AC | 75 ms
9,936 KB |
| testcase_08 | AC | 76 ms
9,940 KB |
| testcase_09 | AC | 2 ms
6,816 KB |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | AC | 2 ms
6,820 KB |
| testcase_21 | AC | 2 ms
6,816 KB |
| testcase_22 | AC | 2 ms
6,820 KB |
| testcase_23 | WA | - |
ソースコード
#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_f1.query(pos + 1, n) + 1;
b2[i] = st_b2.query(0, pos) + 1;
st_b1.update(pos, b1[i]);
st_b2.update(pos, b2[i]);
}
int ans = 0;
rep(i, n) {
chmax(ans, (f1[i] + b1[i]) / 2 - 1);
chmax(ans, (f2[i] + b2[i]) / 2 - 1);
}
printf("%d\n", ans);
}