結果

問題 No.259 セグメントフィッシング＋
ユーザー vain0vain0
提出日時 2015-08-01 00:54:26
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,911 bytes
コンパイル時間 728 ms
コンパイル使用メモリ 78,432 KB
実行使用メモリ 13,764 KB
最終ジャッジ日時 2024-07-18 00:16:50
合計ジャッジ時間 5,673 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
13,764 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 WA -
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 1 ms
6,940 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 154 ms
11,340 KB
testcase_09 AC 156 ms
11,340 KB
testcase_10 AC 155 ms
11,224 KB
testcase_11 AC 156 ms
11,380 KB
testcase_12 AC 156 ms
11,416 KB
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 AC 88 ms
6,944 KB
testcase_24 TLE -
testcase_25 -- -
権限があれば一括ダウンロードができます

ソースコード

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 lef, rig;
int i_lef, i_rig;
int t;
int n, q;

int il(int k) { return (k + i_lef) % n; }
int ir(int k) { return (k + i_rig) % n; }

template<typename Fun>
void print(ST const& st, Fun&& f)
{
	std::cout << "[";
	for ( size_t i = 0; i < n; ++i ) {
		if ( i != 0 ) { std::cout << ", "; }
		std::cout << st.at(f(i));
	}
	std::cout << "]";
}

void moveNext()
{
	auto const tmp = lef.at(il(0));
	lef.update(il(0), rig.at(ir(n - 1)));
	rig.update(ir(n - 1), tmp);

	i_lef = (i_lef + 1) % n;
	i_rig = (i_rig + n - 1) % n;
}

template<typename Fun>
ll query(ST& st, Fun&& f, int y, int z)
{
	if ( y == z ) return 0;
	y = f(y);
	z = f(z);
	if ( y < z ) {
		return st.query(y, z);
	} else {
		return st.query(y, n) + st.query(0, z);
	}
}

int main()
{
	cin >> n >> q;

	lef.init(n);
	rig.init(n);

	rep(i, q)
	{
		int u, y, z;
		char c;
		cin >> c >> u >> y >> z;
		t += ((u - t) / n) * n;
		while ( t < u ) {
			moveNext();
			++t;
		}

		switch ( c ) {
			case 'L':
				lef.update(il(y), lef.at(il(y)) + z);
				break;
			case 'R':
				rig.update(ir(y), rig.at(ir(y)) + z);
				break;
			case 'C': {
				ll s = query(lef, il, y, z) + query(rig, ir, y, z);
				cout << s << endl;
				break;
			}
		}
		ifdebug {
			cout << "t = " << t << endl;
			cout << "lef: "; print(lef, il); cout << endl;
			cout << "rig: "; print(rig, ir); cout << endl;
		}
	}

	return 0;
}
0