結果

問題 No.151 セグメントフィッシング
コンテスト
ユーザー risujiroh
提出日時 2019-01-03 04:09:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 9 ms / 5,000 ms
コード長 1,652 bytes
コンパイル時間 2,007 ms
コンパイル使用メモリ 169,932 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-23 05:48:36
合計ジャッジ時間 3,572 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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);
  };
  int t = 1;
  while (q--) {
    char c; cin >> c;
    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';
    }
    ++t;
  }
}
0