結果
問題 | No.3094 Stapler |
ユーザー |
![]() |
提出日時 | 2025-04-06 19:57:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 7,366 bytes |
コンパイル時間 | 4,583 ms |
コンパイル使用メモリ | 260,152 KB |
実行使用メモリ | 68,852 KB |
最終ジャッジ日時 | 2025-06-20 02:32:38 |
合計ジャッジ時間 | 22,243 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 71 WA * 1 |
ソースコード
#include <bits/stdc++.h> using namespace std; //* #include <atcoder/all> using namespace atcoder; using mint = modint998244353; // using mint = modint1000000007; //*/ using ll = long long; using i128 = __int128_t; using pll = pair<ll, ll>; using tlll = tuple<ll, ll, ll>; using ld = long double; const int INF = 1000100100; const ll INFF = 1000100100100100100LL; const int dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0}; #define overload4(_1, _2, _3, _4, name, ...) name #define rep1(i, n) for (ll i = 0; i < ll(n); i++) #define rep2(i, l, r) for (ll i = ll(l); i < ll(r); i++) #define rep3(i, l, r, d) for (ll i = ll(l); (d) > 0 ? i < ll(r) : i > ll(r); i += d) #define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define per(i, n) for (int i = (n) - 1; i >= 0; --i) #define yesno(f) cout << (f ? "Yes" : "No") << endl; #define YESNO(f) cout << (f ? "YES" : "NO") << endl; #define all(a) (a).begin(), (a).end() #define popc(x) __builtin_popcountll(ll(x)) template <typename S, typename T> ostream &operator<<(ostream &os, const pair<S, T> &p) { return os << p.first << ' ' << p.second; } template <typename T> void printvec(const vector<T> &v) { int n = v.size(); rep(i, n) cout << v[i] << (i == n - 1 ? "" : " "); cout << '\n'; } template <typename T> void printvect(const vector<T> &v) { for (auto &vi : v) cout << vi << '\n'; } template <typename T> void printvec2(const vector<vector<T>> &v) { for (auto &vi : v) printvec(vi); } template <typename S, typename T> bool chmax(S &x, const T &y) { return (x < y) ? (x = y, true) : false; } template <typename S, typename T> bool chmin(S &x, const T &y) { return (x > y) ? (x = y, true) : false; } #ifdef LOCAL // https://zenn.dev/sassan/articles/19db660e4da0a4 #include "cpp-dump-main/dump.hpp" #define dump(...) cpp_dump(__VA_ARGS__) CPP_DUMP_DEFINE_DANGEROUS_EXPORT_OBJECT(val()); #else #define dump(...) #endif struct io_setup { io_setup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout << fixed << setprecision(15); } } io_setup; template <typename S, typename F> struct Lazy_segtree { using FS = function<S(S, S)>; using FA = function<S(F, S)>; using FF = function<F(F, F)>; // F composition(F f, F g): f⚪︎g int n, m, height; FS op; FA mapping; FF composition; const S e; const F id; vector<S> seg; vector<F> lazy; Lazy_segtree(int n_, FS fs_, FA fa_, FF ff_, S e_, F id_) : n(n_), op(fs_), mapping(fa_), composition(ff_), e(e_), id(id_) { m = 1, height = 0; while (m < n) m <<= 1, height++; seg.assign(2 * m, e), lazy.assign(2 * m, id); } Lazy_segtree(vector<S> &n_, FS fs_, FA fa_, FF ff_, S e_, F id_) : n(n_.size()), op(fs_), mapping(fa_), composition(ff_), e(e_), id(id_) { m = 1, height = 0; while (m < n) m <<= 1, height++; seg.assign(2 * m, e), lazy.assign(2 * m, id); copy(begin(n_), end(n_), begin(seg) + m); for (int i = m - 1; i > 0; i--) seg[i] = op(seg[2 * i], seg[2 * i + 1]); build(); } inline S reflect(int i) const { return mapping(lazy[i], seg[i]); } inline void recalc(int i) { while (i >>= 1) seg[i] = op(reflect(2 * i), reflect(2 * i + 1)); } // lazy eval inline void eval(int i) { lazy[2 * i] = composition(lazy[i], lazy[2 * i]); lazy[2 * i + 1] = composition(lazy[i], lazy[2 * i + 1]); seg[i] = reflect(i); lazy[i] = id; } inline void thrust(int i) { for (int j = height; j > 0; j--) eval(i >> j); } //* void set(int i, S x) { seg[i + m] = x; } void build() { for (int i = m - 1; i > 0; i--) seg[i] = op(seg[2 * i], seg[2 * i + 1]); } //*/ void update(int i, S x) { i += m; thrust(i); seg[i] = x; lazy[i] = id; recalc(i); } void apply(int l, int r, const F &x) { l = max(l, 0), r = min(r, n); if (l >= r) return; l += m, r += m; thrust(l), thrust(r - 1); int a = l, b = r; while (l < r) { if (l & 1) lazy[l] = composition(x, lazy[l]), l++; if (r & 1) r--, lazy[r] = composition(x, lazy[r]); l >>= 1, r >>= 1; } recalc(a), recalc(b - 1); } S query(int l, int r) { l = max(l, 0), r = min(r, n); if (l >= r) return e; l += m, r += m; thrust(l), thrust(r - 1); S L = e, R = e; while (l < r) { if (l & 1) L = op(L, reflect(l++)); if (r & 1) R = op(reflect(--r), R); l >>= 1, r >>= 1; } return op(L, R); } S all_() { return query(0, n); } S operator[](int i) { return query(i, i + 1); } template <typename C> int find_subtree(int i, const C &check, S &x, int type) { while (i < m) { eval(i); S nxt = type ? op(reflect(2 * i + type), x) : op(x, reflect(2 * i + type)); if (check(nxt)) { i = 2 * i + type; } else { x = nxt; i = 2 * i + (type ^ 1); } } return i - m; } // check(区間 [l,r] での演算結果) を満たす最小の r (なければ n) template <typename C> int find_first(int l, const C &check) { S L = e; int a = l + m, b = 2 * m; thrust(a); while (a < b) { if (a & 1) { S nxt = op(L, reflect(a)); if (check(nxt)) return find_subtree(a, check, L, 0); L = nxt; a++; } a >>= 1, b >>= 1; } return n; } // check(区間 [l,r) での演算結果) を満たす最大の l (なければ -1) template <typename C> int find_last(int r, const C &check) { S R = e; int a = m, b = r + m; thrust(b - 1); while (a < b) { if ((b & 1) || a == 1) { S nxt = op(reflect(--b), R); if (check(nxt)) return find_subtree(b, check, R, 1); R = nxt; } a >>= 1, b >>= 1; } return -1; } }; struct S { long long mi, cnt; S(long long mi, long long cnt) : mi(mi), cnt(cnt) {} }; using F = long long; S op(S a, S b) { if (a.mi < b.mi) return a; if (a.mi > b.mi) return b; return {a.mi, a.cnt + b.cnt}; } S mapping(F f, S x) { return {x.mi + f, x.cnt}; } F composition(F f, F g) { return f + g; } S e = S(2e18, 0); F id = 0; void solve() { int n, q; cin >> n >> q; vector<S> ini(n - 1, {0, 1}); Lazy_segtree<S, F> seg(ini, op, mapping, composition, e, id); vector<int> l(q), r(q); rep(i, q) { int t; cin >> t; if (t == 1) { cin >> l[i] >> r[i]; l[i]--, r[i]--; seg.apply(l[i], r[i], 1); } if (t == 2) { int id; cin >> id; id--; seg.apply(l[id], r[id], -1); } if (t == 3) { cout << 1 + seg.all_().cnt << endl; } // rep(i, n - 1) { // cout << seg[i].mi << " "; // } // cout << endl; } } int main() { int t; // cin >> t; t = 1; while (t--) { solve(); } }