結果

問題 No.259 セグメントフィッシング＋
ユーザー risujirohrisujiroh
提出日時 2019-01-03 04:12:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 43 ms / 2,000 ms
コード長 1,651 bytes
コンパイル時間 1,692 ms
コンパイル使用メモリ 169,900 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2024-05-02 20:21:50
合計ジャッジ時間 4,995 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 39 ms
6,272 KB
testcase_09 AC 39 ms
6,400 KB
testcase_10 AC 39 ms
6,272 KB
testcase_11 AC 39 ms
6,528 KB
testcase_12 AC 38 ms
6,400 KB
testcase_13 AC 42 ms
6,400 KB
testcase_14 AC 42 ms
6,400 KB
testcase_15 AC 42 ms
6,400 KB
testcase_16 AC 41 ms
6,272 KB
testcase_17 AC 40 ms
6,400 KB
testcase_18 AC 43 ms
6,400 KB
testcase_19 AC 41 ms
6,400 KB
testcase_20 AC 42 ms
6,400 KB
testcase_21 AC 43 ms
6,400 KB
testcase_22 AC 42 ms
6,400 KB
testcase_23 AC 27 ms
5,376 KB
testcase_24 AC 38 ms
6,272 KB
testcase_25 AC 40 ms
6,400 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