結果

問題 No.2338 Range AtCoder Query
ユーザー Carpenters-CatCarpenters-Cat
提出日時 2023-06-27 22:21:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,133 bytes
コンパイル時間 2,216 ms
コンパイル使用メモリ 214,080 KB
最終ジャッジ日時 2025-02-15 02:47:01
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 TLE * 1 -- * 23
権限があれば一括ダウンロードができます

ソースコード

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