結果

問題 No.151 セグメントフィッシング
コンテスト
ユーザー pekempey
提出日時 2015-09-02 16:07:10
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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