結果
| 問題 |
No.973 余興
|
| コンテスト | |
| ユーザー |
 fine
|
| 提出日時 | 2020-01-17 22:26:44 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
MLE
|
| 実行時間 | - |
| コード長 | 6,372 bytes |
| コンパイル時間 | 1,948 ms |
| コンパイル使用メモリ | 176,272 KB |
| 実行使用メモリ | 818,048 KB |
| 最終ジャッジ日時 | 2024-06-25 21:46:34 |
| 合計ジャッジ時間 | 5,348 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | -- * 2 |
| other | MLE * 1 -- * 53 |
ソースコード
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// 参考: http://kazuma8128.hatenablog.com/entry/2017/12/29/081929
template <class MonoidOp>
struct LazySegmentTree {
using Tm = typename MonoidOp::Tm;
using To = typename MonoidOp::To;
int n;
int h;
vector<Tm> data;
vector<To> lazy;
LazySegmentTree() {}
LazySegmentTree(int size, Tm initial_data_value = MonoidOp::unit()) {
n = 1;
h = 0;
while (n < size) {
h++;
n <<= 1;
}
data.assign((n << 1), initial_data_value);
lazy.assign((n << 1), MonoidOp::op_unit());
if (initial_data_value != MonoidOp::unit()) {
for (int i = n - 1; i > 0; i--) data[i] = MonoidOp::merge(data[(i << 1)], data[(i << 1) + 1]);
}
}
LazySegmentTree(const vector<Tm>& v) {
int size = v.size();
n = 1;
h = 0;
while (n < size) {
h++;
n <<= 1;
}
data.assign((n << 1), MonoidOp::unit());
lazy.assign((n << 1), MonoidOp::op_unit());
for (int i = 0; i < size; i++) data[i + n] = v[i];
for (int i = n - 1; i > 0; i--) data[i] = MonoidOp::merge(data[(i << 1)], data[(i << 1) + 1]);
}
// https://komiyam.hatenadiary.org/entry/20131202/1385992406
inline int getSegLen(int k) {
return n / (1 << (31 - __builtin_clz(k)));
}
Tm getLeaf(int k) {
return query(k, k + 1);
}
void push(int k) {
if (lazy[k] == MonoidOp::op_unit()) return;
int seg_len = getSegLen(k);
data[k] = MonoidOp::apply(data[k], lazy[k], seg_len);
if (seg_len > 1) {
lazy[(k << 1)] = MonoidOp::op_merge(lazy[(k << 1)], lazy[k]);
lazy[(k << 1) + 1] = MonoidOp::op_merge(lazy[(k << 1) + 1], lazy[k]);
}
lazy[k] = MonoidOp::op_unit();
}
void update(int k) {
Tm vl = MonoidOp::apply(data[(k << 1)], lazy[(k << 1)], getSegLen(k << 1));
Tm vr = MonoidOp::apply(data[(k << 1) + 1], lazy[(k << 1) + 1], getSegLen((k << 1) + 1));
data[k] = MonoidOp::merge(vl, vr);
}
//区間[a, b)に対する更新
void update(int a, int b, To x) {
a += n, b += n - 1;
for (int i = h; i > 0; i--) {
push(a >> i);
push(b >> i);
}
for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) lazy[l] = MonoidOp::op_merge(lazy[l], x), l++;
if (r & 1) --r, lazy[r] = MonoidOp::op_merge(lazy[r], x);
}
while (a >>= 1, b >>= 1, a) {
if (lazy[a] == MonoidOp::op_unit()) update(a);
if (lazy[b] == MonoidOp::op_unit()) update(b);
}
}
//区間[a, b)に対するクエリに答える
Tm query(int a, int b) {
a += n, b += n - 1;
for (int i = h; i > 0; i--) {
push(a >> i);
push(b >> i);
}
Tm vl = MonoidOp::unit(), vr = MonoidOp::unit();
for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) {
vl = MonoidOp::merge(vl, MonoidOp::apply(data[l], lazy[l], getSegLen(l)));
l++;
}
if (r & 1) {
--r;
vr = MonoidOp::merge(MonoidOp::apply(data[r], lazy[r], getSegLen(r)), vr);
}
}
return MonoidOp::merge(vl, vr);
}
};
// 以下、MonoidOpの例
template<class U = ll, class V = U>
struct RangeSumAdd {
using Tm = U;
using To = V;
static Tm merge(Tm x, Tm y) { return x + y; }
static To op_merge(To x, To y) { return x + y; }
static Tm apply(Tm vm, To vo, int seg_len) { return vm + vo * seg_len; }
static constexpr Tm unit() { return Tm(0); }
static constexpr To op_unit() { return To(0); }
};
template<class U = ll, class V = U>
struct RangeMinUpdate {
using Tm = U;
using To = V;
static Tm merge(Tm x, Tm y) { return min(x, y); }
static To op_merge(To x, To y) { return y; }
static Tm apply(Tm vm, To vo, int seg_len) { return vo == op_unit() ? vm : vo; }
static constexpr Tm unit() { return numeric_limits<Tm>::max(); }
static constexpr To op_unit() { return numeric_limits<To>::max(); }
};
// 作用素の初期値は更新クエリで与えられる値の定義域の範囲外の値にする
template<class U = ll, class V = U>
struct RangeSumUpdate {
using Tm = U;
using To = V;
static Tm merge(Tm x, Tm y) { return x + y; }
static To op_merge(To x, To y) { return y; }
static Tm apply(Tm vm, To vo, int seg_len) { return vo == op_unit() ? vm : vo * seg_len; }
static constexpr Tm unit() { return Tm(0); }
static constexpr To op_unit() { return numeric_limits<To>::min(); }
};
// 初期値 != 単位元 の場合に注意
template<class U = ll, class V = U>
struct RangeMinAdd {
using Tm = U;
using To = V;
static Tm merge(Tm x, Tm y) { return min(x, y); }
static To op_merge(To x, To y) { return x + y; }
static Tm apply(Tm vm, To vo, int seg_len) { return vm + vo; }
static constexpr Tm unit() { return numeric_limits<Tm>::max(); }
static constexpr To op_unit() { return To(0); }
};
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n;
ll x;
cin >> n >> x;
vector<ll> a(n), sum(n + 1, 0);
using Seg = LazySegmentTree< RangeSumUpdate<int> >;
vector<Seg> st_row(n + 1, Seg(n + 1)), st_col(n + 1, Seg(n + 1));
for (int i = 0; i < n; ++i) {
cin >> a[i];
sum[i + 1] = sum[i] + a[i];
st_row[i].update(i, i + 1, 1);
st_col[i].update(i, i + 1, 1);
}
for (int d = 1; d < n; ++d) {
for (int i = 0; i <= n - d; ++i) {
if (st_row[i].query(i + d, i + d + 1) > 0 || st_col[i + d].query(i, i + 1) > 0) continue;
{
int idx = lower_bound(sum.begin(), sum.begin() + i, sum[i] - x) - sum.begin();
if (idx < i) st_col[i + d].update(idx, i, 1);
}
{
int idx = upper_bound(sum.begin() + i + d, sum.end(), x + sum[i + d]) - sum.begin();
if (i + d < idx) st_row[i].update(i + d, idx, 1);
}
}
}
cout << ((st_row[0].query(n, n + 1) > 0 || st_col[n].query(0, 1) > 0) ? "A" : "B") << "\n";
return 0;
}