結果
| 問題 |
No.2861 Slime Party
|
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2025-09-29 09:18:46 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 4,251 bytes |
| コンパイル時間 | 6,395 ms |
| コンパイル使用メモリ | 201,400 KB |
| 実行使用メモリ | 22,400 KB |
| 最終ジャッジ日時 | 2025-09-29 09:19:17 |
| 合計ジャッジ時間 | 22,207 ms |
|
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| other | WA * 11 OLE * 1 -- * 64 |
ソースコード
//ai slop that does not work
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Fenwick (BIT) for point updates, prefix sums
struct Fenwick {
int n;
vector<ll> bit;
Fenwick() {}
Fenwick(int n): n(n), bit(n+1, 0) {}
void add(int idx, ll delta) {
for (; idx <= n; idx += idx & -idx) bit[idx] += delta;
}
ll sumPrefix(int idx) const {
ll res = 0;
for (; idx > 0; idx -= idx & -idx) res += bit[idx];
return res;
}
ll sumRange(int l, int r) const {
if (l > r) return 0;
return sumPrefix(r) - sumPrefix(l-1);
}
};
// Segment tree that stores range maximums of A,
// and supports "first index in [ql,qr] with A[i] >= val"
// and "last index in [ql,qr] with A[i] >= val".
struct SegTreeMax {
int n;
vector<ll> st; // max on interval
SegTreeMax() {}
SegTreeMax(const vector<ll>& A) { build(A); }
void build(const vector<ll>& A) {
n = (int)A.size() - 1; // A is 1-indexed
st.assign(4*n+4, LLONG_MIN);
buildRec(1, 1, n, A);
}
void buildRec(int p, int l, int r, const vector<ll>& A) {
if (l == r) {
st[p] = A[l];
return;
}
int m = (l + r) >> 1;
buildRec(p<<1, l, m, A);
buildRec(p<<1|1, m+1, r, A);
st[p] = max(st[p<<1], st[p<<1|1]);
}
// Find first i in [ql,qr] with A[i] >= val. Return n+1 if none.
int first_ge(int ql, int qr, ll val) const {
if (ql > qr) return n+1;
return firstRec(1, 1, n, ql, qr, val);
}
int firstRec(int p, int l, int r, int ql, int qr, ll val) const {
if (qr < l || r < ql || st[p] < val) return n+1; // none here
if (l == r) return l;
int m = (l + r) >> 1;
int left = firstRec(p<<1, l, m, ql, qr, val);
if (left != n+1) return left;
return firstRec(p<<1|1, m+1, r, ql, qr, val);
}
// Find last i in [ql,qr] with A[i] >= val. Return 0 if none.
int last_ge(int ql, int qr, ll val) const {
if (ql > qr) return 0;
return lastRec(1, 1, n, ql, qr, val);
}
int lastRec(int p, int l, int r, int ql, int qr, ll val) const {
if (qr < l || r < ql || st[p] < val) return 0; // none here
if (l == r) return l;
int m = (l + r) >> 1;
int right = lastRec(p<<1|1, m+1, r, ql, qr, val);
if (right != 0) return right;
return lastRec(p<<1, l, m, ql, qr, val);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
ll L;
if (!(cin >> N >> L)) {
return 0;
}
vector<ll> A(N+1), X(N+1);
for (int i = 1; i <= N; ++i) cin >> A[i];
for (int i = 1; i <= N; ++i) cin >> X[i];
int Q;
cin >> Q;
// Data structures
SegTreeMax segA(A); // static in A (A_i are all distinct and never change)
Fenwick bitX(N); // dynamic in X
for (int i = 1; i <= N; ++i) bitX.add(i, X[i]);
auto solve_for_k = [&](int c) -> ll {
// Start between c and c+1, current level t = L
ll t = L;
// Iterate to least fixed point t = L + sum_X( component of {i | A[i] < t} that touches gap )
while (true) {
// nearest blockers (A[i] >= t) around the gap
int left_blocker = segA.last_ge(1, c, t); // 0 if none
int right_blocker = segA.first_ge(c+1, N, t); // N+1 if none
int L2 = left_blocker + 1;
int R2 = right_blocker - 1;
ll gain = (L2 <= R2) ? bitX.sumRange(L2, R2) : 0LL;
ll t2 = L + gain;
if (t2 == t) return t;
// For safety (shouldn't happen if X_i >= 0): if t2 < t, still stop
if (t2 < t) return t;
t = t2;
}
};
for (int qi = 0; qi < Q; ++qi) {
int type;
cin >> type;
if (type == 1) {
int a; ll b;
cin >> a >> b;
ll delta = b - X[a];
X[a] = b;
bitX.add(a, delta);
} else if (type == 2) {
int c;
cin >> c;
cout << solve_for_k(c) << '\n';
} else {
// unknown query type; consume line if needed
}
}
return 0;
}