結果

問題 No.151 セグメントフィッシング
ユーザー pekempeypekempey
提出日時 2015-09-02 16:07:10
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 59 ms / 5,000 ms
コード長 2,450 bytes
コンパイル時間 2,040 ms
コンパイル使用メモリ 170,352 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-18 17:51:29
合計ジャッジ時間 3,798 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

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

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, a) rep2 (i, 0, a)
#define rep2(i, a, b) for (int i = (a); i < (b); i++)
#define repr(i, a) repr2 (i, 0, a)
#define repr2(i, a, b) for (int i = (b) - 1; i >= (a); i--)
using namespace std;
typedef long long ll;

struct BIT {
	int size;
	vector<ll> bit;
	BIT(int size) : size(size), bit(size + 1) {}
	void add(int k, ll x) {
		k++;
		while (k <= size) {
			bit[k] += x;
			k += k & -k;
		}
	}
	ll sum(int k) {
		k++;
		ll res = 0;
		while (k > 0) {
			res += bit[k];
			k -= k & -k;
		}
		return res;
	}
};

ll modulo(ll a, ll mod) {
	a %= mod; a += mod; a %= mod;
	return a;
}

vector<pair<int, int>> mergeseg(vector<pair<int, int>> seg) {
	vector<pair<int, int>> es;
	int n = seg.size();
	rep (i, n) {
		es.emplace_back(seg[i].first, i);
		es.emplace_back(seg[i].second, i + n);
	}
	sort(es.begin(), es.end());
	int num = 0;
	int left = 0;
	vector<pair<int, int>> res;
	rep (i, es.size()) {
		if (es[i].second < n) {
			if (num == 0) {
				left = es[i].first;	
			}
			num++;
		} else {
			num--;
			if (num == 0) {
				int right = es[i].first;	
				res.emplace_back(left, right);
			}
		}
	}
	return res;
}

ll sum(int l1, int r1, int l2, int r2, BIT &bit, int N) {
	vector<pair<int, int>> seg;
	if (l1 <= r1) {
		seg.emplace_back(l1, r1);
	} else {
		seg.emplace_back(0, r1);
		seg.emplace_back(l1, N * 2 - 1);
	}
	if (l2 <= r2) {
		seg.emplace_back(l2, r2);
	} else {
		seg.emplace_back(0, r2);
		seg.emplace_back(l2, N * 2 - 1);
	}
	seg = mergeseg(seg);
	ll res = 0;
	rep (i, seg.size()) {
		res += bit.sum(seg[i].second) - bit.sum(seg[i].first - 1);
	}
	return res;
}

int main() {
	int N, Q;
	cin >> N >> Q;
	BIT left(N * 3), right(N * 3);
	rep (i, Q) {
		int t = i + 1;
		string x;
		int y, z;
		cin >> x >> y >> z;
		if (x[0] == 'R') {
			y = modulo(y - t, N * 2);
			right.add(y, z);	
		} else if (x[0] == 'L') {
			y = modulo(y + t, N * 2);
			left.add(y, z);
		} else {
			z--;
			ll ans = 0;
			// right
			{
				int l1 = modulo(y - t, N * 2);
				int r1 = modulo(z - t, N * 2);
				int l2 = modulo((N * 2 - 1 - z) - t, N * 2);
				int r2 = modulo((N * 2 - 1 - y) - t, N * 2);
				ans += sum(l1, r1, l2, r2, right, N);
			}
			// left
			{
				int l1 = modulo(y + t, N * 2);
				int r1 = modulo(z + t, N * 2);
				int l2 = modulo((N * 2 - 1 - z) + t, N * 2);
				int r2 = modulo((N * 2 - 1 - y) + t, N * 2);
				ans += sum(l1, r1, l2, r2, left, N);
			}
			cout << ans << endl;
		}
	}

	return 0;
}
0