結果

問題 No.259 セグメントフィッシング+
ユーザー risujirohrisujiroh
提出日時 2019-01-03 04:12:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 40 ms / 2,000 ms
コード長 1,651 bytes
コンパイル時間 1,508 ms
コンパイル使用メモリ 168,708 KB
実行使用メモリ 6,424 KB
最終ジャッジ日時 2023-08-15 08:40:31
合計ジャッジ時間 5,107 ms
ジャッジサーバーID
(参考情報)
judge15 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,384 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 1 ms
4,384 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,380 KB
testcase_08 AC 33 ms
6,136 KB
testcase_09 AC 31 ms
6,208 KB
testcase_10 AC 31 ms
6,204 KB
testcase_11 AC 32 ms
6,088 KB
testcase_12 AC 31 ms
6,212 KB
testcase_13 AC 33 ms
6,164 KB
testcase_14 AC 33 ms
6,292 KB
testcase_15 AC 40 ms
6,080 KB
testcase_16 AC 33 ms
6,204 KB
testcase_17 AC 35 ms
6,204 KB
testcase_18 AC 33 ms
6,152 KB
testcase_19 AC 34 ms
6,108 KB
testcase_20 AC 35 ms
6,084 KB
testcase_21 AC 35 ms
6,100 KB
testcase_22 AC 36 ms
6,424 KB
testcase_23 AC 23 ms
4,380 KB
testcase_24 AC 30 ms
6,100 KB
testcase_25 AC 28 ms
6,200 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


template<class Int> struct FenwickTree {
  const int n, h;

  FenwickTree(int n) : n(n), h(__lg(n) + 1), t(n + 1) {}

  void add(int x, Int a) {
    assert(0 <= x and x < n);
    for (int i = x + 1; i <= n; i += i & -i) t[i] += a;
  }

  Int sum(int x) {
    x = min(x, n);
    Int res = 0;
    for (int i = x; i > 0; i -= i & -i) res += t[i];
    return res;
  }

  Int sum(int l, int r) {
    l = max(0, l), r = min(r, n);
    if (l >= r) return 0;
    return sum(r) - sum(l);
  }

private:
  V<Int> t;
};

int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  int n, q; cin >> n >> q;
  FenwickTree<lint> ft(2 * n);
  auto sum = [&](int l, int r) -> lint {
    l %= 2 * n, r %= 2 * n;
    if (l <= r) return ft.sum(l, r);
    return ft.sum(0, r) + ft.sum(l, ft.n);
  };
  while (q--) {
    char c; cin >> c;
    int t; cin >> t;
    if (c == 'L') {
      int i, a; cin >> i >> a;
      ft.add((i + t) % (2 * n), a);
    } else if (c == 'R') {
      int i, a; cin >> i >> a;
      ft.add((2 * n - 1 - i + t) % (2 * n), a);
    } else {
      int l, r; cin >> l >> r;
      lint res = sum(l + t, r + t) + sum(2 * n - r + t, 2 * n - l + t);
      cout << res << '\n';
    }
  }
}
0