結果

問題 No.2338 Range AtCoder Query
ユーザー Carpenters-CatCarpenters-Cat
提出日時 2023-06-28 00:07:23
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,145 bytes
コンパイル時間 4,368 ms
コンパイル使用メモリ 217,504 KB
実行使用メモリ 137,628 KB
最終ジャッジ日時 2023-09-17 22:45:25
合計ジャッジ時間 9,880 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,056 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,504 KB
testcase_05 AC 2 ms
4,380 KB
testcase_06 AC 4 ms
4,676 KB
testcase_07 AC 5 ms
4,672 KB
testcase_08 AC 5 ms
4,764 KB
testcase_09 AC 5 ms
4,768 KB
testcase_10 AC 5 ms
4,676 KB
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
int main () {
	int N, M, Q;
	cin >> N >> M >> Q;
	std::vector<deque<int>> A(M);
	int ac = 0, wa = 0;
	for (auto& a : A) {
		a.push_front(0);
	}
	vector<int> P(N), X(N);
	for (int i = 0; i < N; i ++) {
		int a;
		string s;
		cin >> a >> s;
		P[i] = --a;
		X[i] = (s == "AC");
	}
	int bk = sqrt(N);
	bk = max(1, bk);
	using T = tuple<int, int, int>;
	vector<T> qu(Q);
	for (int i =0 ; i < Q; i ++) {
		int l, r;
		cin >> l >> r;
		qu[i] = T{--l, r, i};
	}
	sort(qu.begin(), qu.end(), [&](T a, T b) {
		auto& [la, ra, ia] = a;
		auto& [lb, rb, ib] = b;
		if (la / bk != lb / bk) {
			return la / bk < lb / bk;
		} else {
			return ra < rb;
		}
	});
	using pr = pair<int, int>;
	vector<pr> ans(Q);
	int lnow = 0, rnow = 0;
	for (auto [l, r, i] : qu) {
		while (rnow < r) {
			int p = P[rnow];
			if (X[rnow]) {
				if (A[p].size() == 1) {
					wa += A[p].front();
					ac ++;
				}
				// A[p].push_front(-1);
				A[p].push_front(0);
			} else {
				int x = A[p].front();
				A[p].pop_front();
				A[p].push_front(++x);
			}
			rnow ++;
		}
		while (lnow > l) {
			lnow --;
			int p = P[lnow];
			if (X[lnow]) {
				if (A[p].size() != 1) {
					int x = A[p].back();
					wa -= x;
				} else {
					ac ++;
				}
				// A[p].push_back(-1);
				A[p].push_back(0);
			} else {
				if (A[p].size() != 1) {
					wa ++;
				}
				int x = A[p].back();
				A[p].pop_back();
				A[p].push_back(++x);
			}
		}
		while (lnow < l) {
			int p = P[lnow];
			if (X[lnow]) {
				// A[p].pop_back();
				A[p].pop_back();
				if (A[p].size() == 1) {
					ac --;
				} else {
					wa += A[p].back();
				}
			} else {
				if (A[p].size() > 1) {
					wa --;
				}
				int x = A[p].back();
				A[p].pop_back();
				A[p].push_back(--x);
			}
			lnow ++;
		}
		while (rnow > r) {
			rnow --;
			int p = P[rnow];
			if (X[rnow]) {
				// A[p].pop_front();
				A[p].pop_front();
				if (A[p].size() == 1) {
					ac --;
					wa -= A[p].front();
				}
			} else {
				int x = A[p].front();
				A[p].pop_front();
				A[p].push_front(--x);
			}
		}
		ans[i] = pr{ac, wa};
	}
	for (auto [a, c] : ans) {
		printf("%d %d\n", a, c);
	}
}
0