結果
| 問題 | No.618 labo-index |
| コンテスト | |
| ユーザー |
 kuhaku
|
| 提出日時 | 2026-03-15 16:38:08 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,509 bytes |
| 記録 | |
| コンパイル時間 | 1,980 ms |
| コンパイル使用メモリ | 185,312 KB |
| 実行使用メモリ | 11,488 KB |
| 最終ジャッジ日時 | 2026-03-15 16:38:14 |
| 合計ジャッジ時間 | 4,555 ms |
|
ジャッジサーバーID （参考情報） |
judge3_1 / judge2_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 5 WA * 27 RE * 3 |
ソースコード
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/3327
#include <cstdint>
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
/// @brief 座標圧縮
template <class T>
struct coordinate_compression {
coordinate_compression() = default;
coordinate_compression(const std::vector<T> &_data) : data(_data) { build(); }
const T &operator[](int i) const { return data[i]; }
T front() const { return data.front(); }
T back() const { return data.back(); }
void add(T x) { data.emplace_back(x); }
void build() {
std::sort(data.begin(), data.end());
data.erase(std::unique(data.begin(), data.end()), data.end());
}
bool exists(T x) const {
auto it = std::lower_bound(data.begin(), data.end(), x);
return it != data.end() && *it == x;
}
int get(T x) const { return std::distance(data.begin(), std::lower_bound(data.begin(), data.end(), x)); }
int lower_bound(T x) const { return std::distance(data.begin(), std::lower_bound(data.begin(), data.end(), x)); }
int upper_bound(T x) const { return std::distance(data.begin(), std::upper_bound(data.begin(), data.end(), x)); }
std::vector<int> compress(const std::vector<T> &v) const {
int n = v.size();
std::vector<int> res(n);
for (int i = 0; i < n; ++i) res[i] = get(v[i]);
return res;
}
int size() const { return data.size(); }
private:
std::vector<T> data;
};
/// @brief 座標圧縮
template <class T>
std::vector<int> compress(const std::vector<T> &v) {
coordinate_compression cps(v);
std::vector<int> res;
res.reserve(std::size(v));
for (auto &&x : v) res.emplace_back(cps.get(x));
return res;
}
#include <bit>
#include <cassert>
#include <limits>
#include <numeric>
#include <utility>
template <class T>
struct Add {
using value_type = T;
static constexpr T id() { return T(); }
static constexpr T op(const T &lhs, const T &rhs) { return lhs + rhs; }
template <class U>
static constexpr U f(T lhs, U rhs) {
return lhs + rhs;
}
};
template <class T>
struct Mul {
using value_type = T;
static constexpr T id() { return T(1); }
static constexpr T op(const T &lhs, const T &rhs) { return lhs * rhs; }
template <class U>
static constexpr U f(T lhs, U rhs) {
return lhs * rhs;
}
};
template <class T>
struct And {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::max(); }
static constexpr T op(const T &lhs, const T &rhs) { return lhs & rhs; }
template <class U>
static constexpr U f(T lhs, U rhs) {
return lhs & rhs;
}
};
template <class T>
struct Or {
using value_type = T;
static constexpr T id() { return T(); }
static constexpr T op(const T &lhs, const T &rhs) { return lhs | rhs; }
template <class U>
static constexpr U f(T lhs, U rhs) {
return lhs | rhs;
}
};
template <class T>
struct Xor {
using value_type = T;
static constexpr T id() { return T(); }
static constexpr T op(const T &lhs, const T &rhs) { return lhs ^ rhs; }
template <class U>
static constexpr U f(T lhs, U rhs) {
return lhs ^ rhs;
}
};
template <class T>
struct Min {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::max(); }
static constexpr T op(const T &lhs, const T &rhs) { return std::min(lhs, rhs); }
template <class U>
static constexpr U f(T lhs, U rhs) {
return std::min((U)lhs, rhs);
}
};
template <class T>
struct Max {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::lowest(); }
static constexpr T op(const T &lhs, const T &rhs) { return std::max(lhs, rhs); }
template <class U>
static constexpr U f(T lhs, U rhs) {
return std::max((U)lhs, rhs);
}
};
template <class T>
struct Gcd {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::max(); }
static constexpr T op(const T &lhs, const T &rhs) {
return lhs == Gcd::id() ? rhs : (rhs == Gcd::id() ? lhs : std::gcd(lhs, rhs));
}
};
template <class T>
struct Lcm {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::max(); }
static constexpr T op(const T &lhs, const T &rhs) {
return lhs == Lcm::id() ? rhs : (rhs == Lcm::id() ? lhs : std::lcm(lhs, rhs));
}
};
template <class T>
struct Update {
using value_type = T;
static constexpr T id() { return std::numeric_limits<T>::max(); }
static constexpr T op(const T &lhs, const T &rhs) { return lhs == Update::id() ? rhs : lhs; }
template <class U>
static constexpr U f(T lhs, U rhs) {
return lhs == Update::id() ? rhs : lhs;
}
};
template <class T>
struct Affine {
using P = std::pair<T, T>;
using value_type = P;
static constexpr P id() { return P(1, 0); }
static constexpr P op(P lhs, P rhs) { return {lhs.first * rhs.first, rhs.first * lhs.second + rhs.second}; }
};
template <class M>
struct Rev {
using T = typename M::value_type;
using value_type = T;
static constexpr T id() { return M::id(); }
static constexpr T op(T lhs, T rhs) { return M::op(rhs, lhs); }
};
/// @brief セグメント木
/// @see https://noshi91.hatenablog.com/entry/2020/04/22/212649
template <class M>
struct segment_tree {
private:
using T = typename M::value_type;
struct _segment_tree_reference {
private:
segment_tree<M> &self;
int k;
public:
_segment_tree_reference(segment_tree<M> &self, int k) : self(self), k(k) {}
_segment_tree_reference &operator=(const T &x) {
self.set(k, x);
return *this;
}
_segment_tree_reference &operator=(T &&x) {
self.set(k, std::move(x));
return *this;
}
operator T() const { return self.get(k); }
};
public:
segment_tree() : segment_tree(0) {}
explicit segment_tree(int n, T e = M::id()) : segment_tree(std::vector<T>(n, e)) {}
template <class U>
explicit segment_tree(const std::vector<U> &v) : _n(v.size()) {
_size = std::bit_ceil<unsigned>(_n);
_log = std::countr_zero<unsigned>(_size);
data = std::vector<T>(_size << 1, M::id());
for (int i = 0; i < _n; ++i) data[_size + i] = T(v[i]);
for (int i = _size - 1; i >= 1; --i) update(i);
}
const T &operator[](int k) const { return data[k + _size]; }
_segment_tree_reference operator[](int k) { return _segment_tree_reference(*this, k); }
T at(int k) const { return data[k + _size]; }
T get(int k) const { return data[k + _size]; }
void set(int k, T val) {
assert(0 <= k && k < _n);
k += _size;
data[k] = val;
for (int i = 1; i <= _log; ++i) update(k >> i);
}
void reset(int k) { set(k, M::id()); }
T all_prod() const { return data[1]; }
T prod(int a, int b) const {
assert(0 <= a && b <= _n);
T l = M::id(), r = M::id();
for (a += _size, b += _size; a < b; a >>= 1, b >>= 1) {
if (a & 1) l = M::op(l, data[a++]);
if (b & 1) r = M::op(data[--b], r);
}
return M::op(l, r);
}
template <class F>
int max_right(F f) const {
return max_right(0, f);
}
template <class F>
int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(M::id()));
if (l == _n) return _n;
l += _size;
T sm = M::id();
do {
while (l % 2 == 0) l >>= 1;
if (!f(M::op(sm, data[l]))) {
while (l < _size) {
l = (2 * l);
if (f(M::op(sm, data[l]))) {
sm = M::op(sm, data[l]);
l++;
}
}
return l - _size;
}
sm = M::op(sm, data[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <class F>
int min_left(F f) const {
return min_left(_n, f);
}
template <class F>
int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(M::id()));
if (r == 0) return 0;
r += _size;
T sm = M::id();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(M::op(data[r], sm))) {
while (r < _size) {
r = (2 * r + 1);
if (f(M::op(data[r], sm))) {
sm = M::op(data[r], sm);
r--;
}
}
return r + 1 - _size;
}
sm = M::op(data[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, _size, _log;
std::vector<T> data;
void update(int k) { data[k] = M::op(data[2 * k], data[2 * k + 1]); }
};
struct S {
std::int64_t x, s;
};
struct M {
using T = S;
using value_type = T;
static constexpr T id() {
return T(std::numeric_limits<std::int64_t>::max(), 0);
}
static constexpr T op(const T& lhs, const T& rhs) {
return S{std::min(lhs.x, rhs.x), lhs.s + rhs.s};
}
};
int main(void) {
int q;
std::cin >> q;
std::vector<int> t(q), x(q);
for (int i = 0; i < q; ++i) std::cin >> t[i] >> x[i];
std::int64_t s = 0;
std::vector<std::int64_t> a;
for (int i = 0; i < q; ++i) {
if (t[i] == 1)
a.emplace_back(x[i] - s);
else if (t[i] == 3)
s += x[i];
}
s = 0;
coordinate_compression cps(a);
segment_tree<M> st(cps.size());
std::vector<int> c;
for (int i = 0; i < q; ++i) {
if (t[i] == 1) {
int k = cps.get(x[i] - s);
c.emplace_back(x[i] - s);
st.set(k, S{x[i] - s, st.get(k).s + 1});
} else if (t[i] == 2) {
int k = cps.get(c[x[i] - 1]);
st.set(k, S{c[x[i] - 1], st.get(k).s - 1});
} else {
s += x[i];
}
auto f = [&](S y) {
return y.x + s >= y.s;
};
int k = st.min_left(f);
auto t = st.prod(k, cps.size());
std::int64_t ans = std::min(t.x + s, t.s);
if (k > 0) {
t = st.prod(k - 1, cps.size());
ans = std::max(ans, std::min(t.x + s, t.s));
}
std::cout << ans << '\n';
}
return 0;
}