結果

問題 No.259 セグメントフィッシング＋
ユーザー vain0vain0
提出日時 2015-08-01 02:11:24
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 150 ms / 2,000 ms
コード長 3,542 bytes
コンパイル時間 762 ms
コンパイル使用メモリ 78,104 KB
実行使用メモリ 11,440 KB
最終ジャッジ日時 2024-07-18 00:20:46
合計ジャッジ時間 4,399 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 1 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 133 ms
11,364 KB
testcase_09 AC 136 ms
11,228 KB
testcase_10 AC 133 ms
11,288 KB
testcase_11 AC 130 ms
11,268 KB
testcase_12 AC 131 ms
11,268 KB
testcase_13 AC 144 ms
11,404 KB
testcase_14 AC 140 ms
11,228 KB
testcase_15 AC 147 ms
11,228 KB
testcase_16 AC 145 ms
11,288 KB
testcase_17 AC 141 ms
11,228 KB
testcase_18 AC 144 ms
11,300 KB
testcase_19 AC 150 ms
11,292 KB
testcase_20 AC 142 ms
11,364 KB
testcase_21 AC 142 ms
11,360 KB
testcase_22 AC 150 ms
11,284 KB
testcase_23 AC 75 ms
6,940 KB
testcase_24 AC 97 ms
11,220 KB
testcase_25 AC 101 ms
11,440 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <string>
#include <vector>
#include <array>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
using namespace std;
using ull = unsigned long long; using ll = long long;
#define repi(_I, _B, _E) for(int _I = (_B); (_I) < (_E); ++ (_I))
#define rep(_I, _N) for(int _I = 0; (_I) < (_N); ++ (_I))
#define all(_X) begin(_X), end(_X)
#ifdef _LOCAL
# define ifdebug //
#else
# define ifdebug if (false)
#endif

//(T, +) semigroup
template<typename T>
struct AddSemigroup
{
	static T operate(T const& lhs, T const& rhs) { return lhs + rhs; }
	static T unit() { return 0; }
};

template<typename T>
T heightInt(T n)
{
	if ( n == 1 ) return 1;
	T h = 0;
	for ( ; n > static_cast<T>(1 << h); ++h );
	return h;
}

template<typename T, typename Semigroup>
class SegTree
{
	using uint = unsigned int;
	std::vector<T> v_;
	uint n_;
	uint h_;
public:
	void init(int n)
	{
		n_ = n;
		h_ = (heightInt<uint>(n));
		assert(n > 1);
		v_.resize((1 << h_) * 2 - 1, Semigroup::unit());
	}
private:
	int nodeIndexFromArrayIndex(int k) const
	{
		assert(0 <= k && static_cast<uint>(k) < n_);
		return ((1 << h_) - 1) + k;
	}
public:
	T const& at(int k) const { return v_[nodeIndexFromArrayIndex(k)]; }
	void update(int k, T const& x)
	{
		uint i = nodeIndexFromArrayIndex(k);
		if ( v_[i] == x ) return;
		v_[i] = x;

		while ( i != 0 ) {
			uint const parent = (i - 1) / 2;
			uint const child = parent * 2 + 1;
			v_[parent] = Semigroup::operate(v_[child], v_[child + 1]);
			i = parent;
		}
	}
public:
	T query(uint begin, uint end)
	{
		if ( begin >= end ) return Semigroup::unit();
		return queryRec(0, 0, 1 << h_, begin, end);
	}
private:
	T queryRec(uint i, uint nodeBeg, uint nodeEnd, uint queryBeg, uint queryEnd)
	{
		assert(nodeBeg <= queryBeg && queryBeg < queryEnd && queryEnd <= nodeEnd);
		uint const nodeMid = nodeBeg + (nodeEnd - nodeBeg + 1) / 2;
		if ( nodeBeg == queryBeg && nodeEnd == queryEnd ) {
			return v_[i];
		} else if ( queryEnd <= nodeMid ) {
			return queryRec(i * 2 + 1, nodeBeg, nodeMid, queryBeg, queryEnd);
		} else if ( nodeMid <= queryBeg ) {
			return queryRec(i * 2 + 2, nodeMid, nodeEnd, queryBeg, queryEnd);
		} else {
			assert(queryBeg < nodeMid && nodeMid < queryEnd);
			auto const& lhs = queryRec(i * 2 + 1, nodeBeg, nodeMid, queryBeg, nodeMid);
			auto const& rhs = queryRec(i * 2 + 2, nodeMid, nodeEnd, nodeMid, queryEnd);
			return Semigroup::operate(lhs, rhs);
		}
	}
};

using ST = SegTree<ll, AddSemigroup<ll>>;
ST st;
int t;
int n, q;

int il(int k) { return (t + 0 + k) % (2*n); }
int ir(int k) { return (t + n + (n - 1 - k)) % (2*n); }

ll query(int y, int z)
{
	if ( y < z ) {
		return st.query(y, z);
	} else {
		return st.query(y, 2*n) + st.query(0, z);
	}
}

int main()
{
	cin >> n >> q;
	st.init(n * 2);

	rep(i, q)
	{
		int u, y, z;
		char c;
		cin >> c >> u >> y >> z;
		t = u;
		switch ( c ) {
			case 'L':
				st.update(il(y), st.at(il(y)) + z);
				break;
			case 'R':
				st.update(ir(y), st.at(ir(y)) + z);
				break;
			case 'C': {
				int const yl = il(y),     zl = il(z);
				int const yr = ir(z - 1), zr = ir(y - 1);
				auto const sl = query(yl, zl);
				auto const sr = query(yr, zr);
				cout << (sl + sr) << endl;
				break;
			}
		}
		ifdebug {
			cout << "t = " << t << endl;
			cout << "[";
			rep(i, n)
			{
				cout << st.at(il(i)) << ", ";
			}
			cout << endl << " ";
			rep(i, n)
			{
				cout << st.at(ir(i)) << ", ";
			}
			cout << "]" << endl;
		}
	}

	return 0;
}
0