#1191477 (C++23) No.152 貯金箱の消失

• 問題: No.152 貯金箱の消失
• ユーザー: T1610
• 提出日時: 2026-10-04 22:46:00
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: WA
• 実行時間: -
• コード長: 2,935 bytes
• コンパイル時間: 3,987 ms
• コンパイル使用メモリ: 380,848 KB
• 実行使用メモリ: 1,208,248 KB
• 最終ジャッジ日時: 2026-10-04 22:46:10
• 合計ジャッジ時間: 7,664 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge3_0

ファイルパターン	結果
other	WA * 8 MLE * 4

ソースコード

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using namespace atcoder;
#define rep(i, n) REP(i, 0, n)
#define REP(i, s, e) for (ll i = (s); i < (ll)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for (ll i = (ll)(s - 1); i >= (ll)(e); i--)
#define all(r) r.begin(), r.end()
#define rall(r) r.rbegin(), r.rend()

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;

template <typename T, typename U>
bool chmax(T& a, const U& b) {
    if (a >= b) return false;
    a = b;
    return true;
}
template <typename T, typename U>
bool chmin(T& a, const U& b) {
    if (a <= b) return false;
    a = b;
    return true;
}

void yes_no(bool f, string yes = "Yes", string no = "No") {
    cout << (f ? yes : no) << "\n";
}

// 円環上の 閉区間 [L, R] の和を安全に取得するヘルパー関数
template <typename Seg>
ll query_closed(Seg& seg, ll L, ll R, ll m) {
    if (L > R) return 0;                 // 区間が空の場合は0
    ll len = R - L + 1;                  // 閉区間なので +1
    if (len >= m) return seg.prod(0, m); // 1周以上なら全体和

    L = (L % m + m) % m; // 負数対応の剰余
    if (L + len <= m) {
        // 区間が m を跨がない場合
        return seg.prod(L, L + len);
    } else {
        // 区間が m を跨ぐため、2つに分割して取得する
        return seg.prod(L, m) + seg.prod(0, L + len - m);
    }
}

void solve() {
    int n, q;
    cin >> n >> q;
    int m = 2 * n;
    segtree<ll, [](ll a, ll b) { return a + b; }, []() { return 0LL; }> segL(m + 10);
    segtree<ll, [](ll a, ll b) { return a + b; }, []() { return 0LL; }> segR(m + 10);
    rep(t, q) {
        char x;
        ll y, z;
        cin >> x >> y >> z;
        if (x == 'L') {
            int cur = (y + t) % m;
            segL.set(cur, segL.get(cur) + z);
        } else if (x == 'R') {
            int cur = (y - t) % m;
            if (cur < 0) cur += m;
            segR.set(cur, segR.get(cur) + z);
        } else {
            ll ans = 0;
            --z;
            // 1. そのままの区間 A: [y, z] (閉区間)
            ans += query_closed(segL, y + t, z + t, m);
            ans += query_closed(segR, y - t, z - t, m);

            // 2. 反射を考慮した区間 B: [2N - min(N-1, z), 2N - max(1, y)]
            // y=0 や z=N のときは区間Aと重なるため、min/max で重複を排除する
            ll b_L = m - min(n - 1, (int)z);
            ll b_R = m - max(1, (int)y);

            if (b_L <= b_R) { // 区間が存在するときだけ加算
                ans += query_closed(segL, b_L + t, b_R + t, m);
                ans += query_closed(segR, b_L - t, b_R - t, m);
            }
            cout << ans << "\n";
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t = 1;
    // multi-testcase
    // cin >> t;
    rep(ti, t) solve();
    return 0;
}