結果

問題 No.833 かっこいい電車
ユーザー YDK1727YDK1727
提出日時 2019-05-25 01:56:46
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 1,743 bytes
コンパイル時間 1,601 ms
コンパイル使用メモリ 168,720 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-07-02 03:51:58
合計ジャッジ時間 3,515 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 43 ms
6,812 KB
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 2 ms
6,944 KB
testcase_07 WA -
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 5 ms
6,944 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 AC 26 ms
6,944 KB
testcase_31 AC 40 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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;

#define int long long

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()
{
  iostreamBooster();

  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