結果
問題 |
No.833 かっこいい電車
|
ユーザー |
![]() |
提出日時 | 2019-07-05 21:44:34 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 170 ms / 2,000 ms |
コード長 | 1,795 bytes |
コンパイル時間 | 2,161 ms |
コンパイル使用メモリ | 171,196 KB |
実行使用メモリ | 9,856 KB |
最終ジャッジ日時 | 2024-07-02 05:46:40 |
合計ジャッジ時間 | 5,181 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<ll,ll> P; #define repi(i,a,b) for(ll i=a;i<b;i++) #define rep(i,a) repi(i,0,a) #define rrep(i,a) for(ll i=a-1;i>=0;i--) //debug #define debug(arr) cerr<<#arr<<"(l"<<__LINE__<<") : ";for(auto x:arr)cerr<<x<<" ";cerr<<endl; template< typename Monoid > struct SegmentTree { using F = function< Monoid(Monoid, Monoid) >; ll sz; vector< Monoid > seg; const F f; const Monoid M1; SegmentTree(ll n, const F f, const Monoid &M1) : f(f), M1(M1) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz, M1); } void set(ll k, const Monoid &x) { seg[k + sz] = x; } void build() { for(ll k = sz - 1; k > 0; k--) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } void update(ll k, const Monoid &x) { k += sz; seg[k] = x; while(k >>= 1) { seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]); } } Monoid query(ll a, ll b) { Monoid L = M1, R = M1; for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if(a & 1) L = f(L, seg[a++]); if(b & 1) R = f(seg[--b], R); } return f(L, R); } Monoid operator[](const ll &k) const { return seg[k + sz]; } }; ll f(ll a, ll b){ return a + b; } int main(){ ll N, Q; cin >> N >> Q; SegmentTree<ll> seg(N, f, 0); rep(i, N){ ll a; cin >> a; seg.set(i, a); } seg.build(); set<ll> beginning; rep(i, N+1) beginning.insert(i); rep(_, Q){ ll q, x; cin >> q >> x; if(q == 1){ beginning.erase(x); } else if(q == 2){ beginning.insert(x); } else if(q == 3){ seg.update(x-1, seg[x-1] + 1); } else{ auto it = beginning.upper_bound(x-1); cout << seg.query(*prev(it), *it) << endl; } } return 0; }