結果

問題 No.151 セグメントフィッシング
ユーザー ctyl_0ctyl_0
提出日時 2015-11-04 02:29:37
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 42 ms / 5,000 ms
コード長 2,384 bytes
コンパイル時間 849 ms
コンパイル使用メモリ 89,228 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-13 12:21:45
合計ジャッジ時間 2,037 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 1 ms
6,812 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 8 ms
6,940 KB
testcase_09 AC 7 ms
6,940 KB
testcase_10 AC 7 ms
6,940 KB
testcase_11 AC 8 ms
6,940 KB
testcase_12 AC 26 ms
6,940 KB
testcase_13 AC 27 ms
6,944 KB
testcase_14 AC 27 ms
6,944 KB
testcase_15 AC 26 ms
6,940 KB
testcase_16 AC 27 ms
6,940 KB
testcase_17 AC 16 ms
6,944 KB
testcase_18 AC 17 ms
6,944 KB
testcase_19 AC 41 ms
6,940 KB
testcase_20 AC 42 ms
6,944 KB
testcase_21 AC 18 ms
6,940 KB
testcase_22 AC 18 ms
6,944 KB
testcase_23 AC 22 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <sstream>
#include <string>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define var auto
#define mod 1000000007
#define inf 2147483647
typedef long long ll;

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
}

template <typename T>
void output(T a, int precision) {
    if(precision > 0){
        cout << fixed << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

// end of template
struct bit {
    vector<ll> v; // 部分和をbitで管理 仮想配列はa[1...n]
    bit(int n){ // bit(int n) : v(n + 1) {}
        v.resize(n + 1);
    }
    
    ll sum(int i){ // 仮想配列a[1]~a[i]の和を求める
        ll ret = 0;
        for(; i > 0; i -= i & -i){ // i & -i: iの1が立っている最高位bitをの2^を返す
            ret += v[i];
        }
        return ret;
    }
    
    void add(int i, ll w) { // index:iにwを加える
        for (; i < v.size(); i += i & -i) {
            v[i] += w;
        }
    }
};

int N;

int mod2N(int i){ // return 1 ~ 2N
    i -= 1;
    return ((i % (2 * N)) + 2 * N) % (2 * N) + 1;
}

int main() {
    // source code
    
    N = inputValue();
    int Q = inputValue();
    
    bit b(2 * N);
    rep(i, Q){
        char c;
        cin >> c;
        int t = i;
        // int t = inputValue(); // セグメントフィッシング+
        int y = inputValue();
        int z = inputValue();
        
        if (c == 'R') { // right
            b.add(mod2N(y - t + 1), z);
        }
        if (c == 'L') { // left
            b.add(mod2N(2 * N - y - t), z);
        }
        if (c == 'C') { // count
            int l1 = mod2N(y - t);
            int r1 = mod2N(z - t);
            int l2 = mod2N(2 * N - z - t);
            int r2 = mod2N(2 * N - y - t);
            
            ll ret1 = b.sum(r1) - b.sum(l1);
            ll ret2 = b.sum(r2) - b.sum(l2);
            if (l1 > r1) {
                ret1 += b.sum(2 * N);
            }
            if (l2 > r2) {
                ret2 += b.sum(2 * N);
            }
            
            output(ret1 + ret2, 0);
        }
        
    }
    
    return 0;
}
0