結果

問題 No.259 セグメントフィッシング＋
ユーザー koyumeishi
提出日時 2015-07-31 23:03:08
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 152 ms / 2,000 ms
コード長 2,189 bytes
コンパイル時間 590 ms
コンパイル使用メモリ 80,760 KB
実行使用メモリ 12,600 KB
最終ジャッジ日時 2024-07-17 23:21:35
合計ジャッジ時間 4,396 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <cstdio>
#include <sstream>
#include <map>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
template<class T>
class BinaryIndexedTree_0_indexed{
    void init(const vector<T> &A){
        for(int i=0; i<N; i++){
            add(i+1, A[i]);
        }
    }
    
public:
    vector<T> tree;
    int N;
    
    BinaryIndexedTree_0_indexed(const int n) : tree(n+1,0), N(n){
        
    }
    
    BinaryIndexedTree_0_indexed(const vector<T> &A) : tree(A.size()+1,0), N(A.size()){
        init(A);
    }
    //caution : position "i" must be 0-indexed
    void add(int i, const T x){
        i += 1;
        while(i <= N){
            tree[i] += x;
            i += i & -i;
        }
    }
    //get sums [0,i]
    T get_sum(int i){
        i += 1;
        T ret=0;
        while(i>0){
            ret += tree[i];
            i -= i & -i;
        }
        return ret;
    }
    //get sums [from,to]
    T get_sums_range(const int from, const int to){
        return get_sum(to) - get_sum(from-1);
    }
    //get at [i]
    T get_at(const int i){
        return get_sum(i) - get_sum(i-1);
    }
    void print(){
        for(int i=0; i<N; i++){
            cerr << get_at(i) << " ";
        }
        cerr << endl;
    }
};
int main(){
    int N,Q;
    cin >> N >> Q;
    int NN = 2*N;
    vector<BinaryIndexedTree_0_indexed<long long>> BIT(2, BinaryIndexedTree_0_indexed<long long>(NN));
    while(Q--){
        string x;
        int t;
        int y,z;
        cin >> x >> t >> y >> z;
        if(x=="R"){
            y += N;
            y = (y - t%(NN) + NN) % (NN);
            BIT[0].add(y, z);
        }else if(x=="L"){
            y += N;
            y = (y + t%(NN) + NN) % (NN);
            BIT[1].add(y, z);
        }else{
            z--;
            long long ans = 0;
            for(int k=0; k<2; k++){
                vector<int> L(2);
                vector<int> R(2);
                L[0] = (-z + (N-1) + (k%2==0?-1:+1)*t%(NN) + NN)%(NN) ;
                R[0] = (-y + (N-1) + (k%2==0?-1:+1)*t%(NN) + NN)%(NN) ;
                L[1] = (+y + N + (k%2==0?-1:+1)*t%(NN) + NN)%(NN) ;
                R[1] = (+z + N + (k%2==0?-1:+1)*t%(NN) + NN)%(NN) ;
                for(int i=0; i<2; i++){
                    if(L[i] > R[i]){
                        ans += BIT[k].get_sums_range(L[i],NN-1);
                        ans += BIT[k].get_sums_range(0,R[i]);
                    }else{
                        ans += BIT[k].get_sums_range(L[i],R[i]);
                    }
                }
            }
            //cout << ans << endl;
            printf("%lld\n", ans);
        }
/*
        for(int i=0; i<2; i++){
            BIT[i].print();
        }
*/
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0