結果

問題 No.833 かっこいい電車
ユーザー YDK1727
提出日時 2019-05-25 01:35:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,697 bytes
コンパイル時間 1,633 ms
コンパイル使用メモリ 171,340 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-02 03:51:34
合計ジャッジ時間 4,940 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 5 WA * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
#define ALL(x) x.begin(), x.end()
#define iostreamBooster() do{ cin.tie(nullptr); ios_base::sync_with_stdio(false); }while(0)
#define rep(i, s, n) for(i64 i=(s); i < (n); ++i)
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
template<class A, class B>inline bool chmax(A &a, const B &b){return b>a ? a=b,1 : 0;}
template<class A, class B>inline bool chmin(A &a, const B &b){return b<a ? a=b,1 : 0;}
constexpr int INF  = 0x3f3f3f3f;
constexpr i64 LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int MOD  = int(1e9) + 7;

template <class T>
struct FenwickTree {
  vector<T> dat;
  explicit FenwickTree(int size): dat(size+5, 0) {}
  void add(int i, const T&v) { while (i < dat.size()) dat[i]+=v, i += i&-i; }
  inline T sum(int i) const { return i <= 0 ? 0 : dat[i] + sum(i & (i-1)); }
  inline T sum(int s, int t) const { return sum(t) - sum(s-1); }

  inline int lowerBound(int v) const {
    int l = 0,  r = dat.size();
    while(r - l > 1) {
      const int mid = (l + r) / 2;
      ((sum(mid) >= v) ? r : l) = mid;
    }
    return r;
  }
};


signed main()
{
  int N, Q;
  cin >> N >> Q;

  FenwickTree<i64> val(N);
  FenwickTree<int> u(N);

  rep(i, 1, N+1) {
    int a; cin >> a;
    val.add(i, a);
    u.add(i, 1);
  }

  rep(q_, 0, Q) {
    int com, x;
    cin >> com >> x;

    if (com == 1) {
      u.add(x+1, -1);
    }
    else if (com == 2) {
      u.add(x+1, +1);
    }
    else if (com == 3) {
      val.add(x, 1);
    }
    else {
      const int blockIdx = u.sum(x);
      const int left = u.lowerBound(blockIdx);
      const int right = u.lowerBound(blockIdx + 1) - 1;
      cout << val.sum(left, right) << '\n';
    }

  }

  return 0;
}
0