結果
問題 |
No.833 かっこいい電車
|
ユーザー |
![]() |
提出日時 | 2022-12-08 13:43:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 135 ms / 2,000 ms |
コード長 | 3,312 bytes |
コンパイル時間 | 1,671 ms |
コンパイル使用メモリ | 172,232 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-14 11:47:34 |
合計ジャッジ時間 | 5,695 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#pragma GCC optimization ("O3") #include <bits/stdc++.h> using namespace std; using ll = long long; using vec = vector<ll>; using mat = vector<vec>; using pll = pair<ll,ll>; #define INF (1LL<<61) #define MOD 1000000007LL // #define MOD 998244353LL #define EPS (1e-10) #define PR(x) cout << (x) << endl #define PS(x) cout << (x) << " " #define REP(i,m,n) for(ll (i)=(m),(i_len)=(n);(i)<(i_len);++(i)) #define FORE(i,v) for(auto (i):v) #define ALL(x) (x).begin(), (x).end() #define SZ(x) ((ll)(x).size()) #define REV(x) reverse(ALL((x))) #define ASC(x) sort(ALL((x))) #define DESC(x) {ASC((x)); REV((x));} #define BIT(s,i) (((s)>>(i))&1) #define pb push_back #define fi first #define se second template<class T> inline int chmin(T& a, T b) {if(a>b) {a=b; return 1;} return 0;} template<class T> inline int chmax(T& a, T b) {if(a<b) {a=b; return 1;} return 0;} class mint { public: ll x; mint(ll x=0) : x((x%MOD+MOD)%MOD) {} mint operator-() const {return mint(-x);} mint& operator+=(const mint& a) {if((x+=a.x)>=MOD) x-=MOD; return *this;} mint& operator-=(const mint& a) {if((x+=MOD-a.x)>=MOD) x-=MOD; return *this;} mint& operator*=(const mint& a) {(x*=a.x)%=MOD; return *this;} mint operator+(const mint& a) const {mint b(*this); return b+=a;} mint operator-(const mint& a) const {mint b(*this); return b-=a;} mint operator*(const mint& a) const {mint b(*this); return b*=a;} mint pow(ll t) const {if(!t) return 1; mint a=pow(t>>1); return (t&1?*this*a:a)*a;} mint inv() const {return pow(MOD-2);} mint& operator/=(const mint& a) {return *this*=a.inv();} mint operator/(const mint& a) const {mint b(*this); return b/=a;} }; istream &operator>>(istream& is, mint& a) {ll t; is>>t; a=t; return is;} ostream &operator<<(ostream& os, const mint& a) {return os<<a.x;} template <typename T> struct BinaryIndexedTree { int n; vector<T> dat; BinaryIndexedTree(int n_) { n = n_+1; dat = vector<T>(n, 0); } void add(int i, T x) { for(int idx=i; idx<n; idx+=(idx&-idx)) dat[idx] += x; } T sum(int i) { T s(0); for(int idx=i; idx>0; idx-=(idx&-idx)) s += dat[idx]; return s; } int lower_bound(T w) { if(w <= 0) return 0; else { int x = 0, r = 1; while(r < n) r <<= 1; for(int len=r; len>0; len>>=1) { if(x+len < n && dat[x+len] < w) { w -= dat[x+len]; x += len; } } return x+1; } } }; int main() { ll N, Q; cin >> N >> Q; BinaryIndexedTree<ll> bit1(N+1), bit2(N+1); REP(i,1,N+1) { ll a; cin >> a; bit1.add(i, a); bit2.add(i, 1); } while(Q--) { ll t, x; cin >> t >> x; if(t == 1) { if(bit2.sum(x+1)-bit2.sum(x) == 1) bit2.add(x+1, -1); } else if(t == 2) { if(bit2.sum(x+1)-bit2.sum(x) == 0) bit2.add(x+1, 1); } else if(t == 3) bit1.add(x, 1); else if(t == 4) { ll k = bit2.sum(x); ll l = bit2.lower_bound(k); ll r = bit2.lower_bound(k+1); PR(bit1.sum(r-1)-bit1.sum(l-1)); } } return 0; } /* */