結果

問題 No.259 セグメントフィッシング＋
ユーザー hirokazu1020hirokazu1020
提出日時 2015-07-31 23:47:32
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 126 ms / 2,000 ms
コード長 1,656 bytes
コンパイル時間 887 ms
コンパイル使用メモリ 83,004 KB
実行使用メモリ 6,400 KB
最終ジャッジ日時 2024-12-23 14:17:52
合計ジャッジ時間 5,083 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<sstream>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
using namespace std;
#define INF (1<<29)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()
#define uniq(v) v.erase(unique(all(v)),v.end())
#define indexOf(v,x) (find(all(v),x)-v.begin())




class BIT{
	std::vector<long long> bit;
public:
	BIT(int size):bit(size+1,0){}
	void add(int i,int x){//i番目にx加える
		i++;
		while(i<(int)bit.size()){
			bit[i]+=x;
			i+= i&-i;
		}
	}
	long long sum(int a)const{//[0,a]の和
		a++;
		long long res=0;
		while(0<a){
			res+=bit[a];
			a-= a&-a;
		}
		return res;
	}
	long long sum(int a,int b)const{//[a,b]の合計
		return sum(b)-sum(a-1);
	}
	void zeroclear(){
		bit.assign(bit.size(),0);
	}
};


int n,q;

int code(char dir,int x,int t){
	int ret;
	if(dir=='R'){
		ret = x;
	}else{
		ret = n+(n-x-1);
	}
	return (ret-t%(2*n)+2*n)%(2*n);
}

long long sum(BIT &bit,int s,int e){
	if(s<=e){
		return bit.sum(s,e);
	}else{
		return bit.sum(2*n-1)-bit.sum(s-1)+bit.sum(e);
	}
}


int main(){
	cin>>n>>q;
	BIT bit(2*n);
	rep(_,q){
		char x;
		int t,y,z;
		cin>>x>>t>>y>>z;
		if(x=='R'){
			int val=code('R',y,t);
			bit.add(val,z);
		}else if(x=='L'){
			int val=code('L',y,t);
			bit.add(val,z);
		}else{
			z=min(z-1,n-1);
			long long ans=0;
			int s,e;
			s=code('R',y,t);
			e=code('R',z,t);
			ans+=sum(bit,s,e);
			s=code('L',z,t);
			e=code('L',y,t);
			ans+=sum(bit,s,e);
			cout<<ans<<endl;
		}
	}
	return 0;
}
0