結果
問題 | No.2338 Range AtCoder Query |
ユーザー |
|
提出日時 | 2023-06-02 22:59:38 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 2,823 ms / 4,000 ms |
コード長 | 3,587 bytes |
コンパイル時間 | 6,701 ms |
コンパイル使用メモリ | 91,788 KB |
実行使用メモリ | 127,308 KB |
最終ジャッジ日時 | 2025-01-03 04:15:09 |
合計ジャッジ時間 | 69,448 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 34 |
ソースコード
import java.io.PrintWriter;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Scanner;public class Main {public static void main(String[] args) {new Main().run();}final long p=998244353;final long g=3;int MAX = 5000;long[] fac = new long[MAX];long[] ifac = new long[MAX];long[] inv = new long[MAX];{Arrays.fill(fac, 1);Arrays.fill(ifac, 1);Arrays.fill(inv, 1);for (int i = 2; i < MAX; ++i) {fac[i] = i * fac[i - 1] % p;inv[i] = p - inv[(int) (p % i)] * (p / i) % p;ifac[i] = inv[i] * ifac[i - 1] % p;}}class Tree {int[] v;int n;public Tree(int n_) {n = Integer.highestOneBit(n_) * 2;v = new int[2 * n];}void add(int k, int val) {int pos = id(k, k + 1);v[pos] += val;while (pos != id(0, n)) {pos /= 2;v[pos] = v[2 * pos] + v[2 * pos + 1];}}void set(int k, int val) {int pos = id(k, k + 1);v[pos] = val;while (pos != id(0, n)) {pos /= 2;v[pos] = v[2 * pos] + v[2 * pos + 1];}}int query(int a, int b) {if (b - a <= 0) return 0;int ma = a + Integer.lowestOneBit(a);int mb = b - Integer.lowestOneBit(b);if (a < ma && ma <= b) {return v[id(a, ma)] + query(ma, b);} else {return query(a, mb) + v[id(mb, b)];}}int id(int a, int b) {int w = b - a;return a / w + n / w;}}void run() {Scanner sc = new Scanner(System.in);int N = sc.nextInt();int M = sc.nextInt();int Q = sc.nextInt();int[] P = new int[N];boolean[] ac = new boolean[N];for (int i = 0; i < N; ++i) {P[i] = sc.nextInt() - 1;ac[i] = sc.next().equals("AC");}int[][] query = new int[Q][3];int[] ans1 = new int[Q];int[] ans2 = new int[Q];for (int i = 0; i < Q; ++i) {query[i][0] = sc.nextInt() - 1;query[i][1] = sc.nextInt() - 1;query[i][2] = i;}Arrays.sort(query, (x, y) -> -Integer.compare(x[0], y[0]));Tree watree = new Tree(N);Tree actree = new Tree(N);Tree petree = new Tree(N);ArrayDeque<Integer>[] walist = new ArrayDeque[M];ArrayDeque<Integer>[] aclist = new ArrayDeque[M];for (int i = 0; i < M; ++i) {aclist[i] = new ArrayDeque<>();walist[i] = new ArrayDeque<>();}int p = 0;for (int src = N - 1; src >= 0; --src) {if (!ac[src]) {walist[P[src]].addFirst(src);watree.set(src, 1);petree.set(src, -1);if (!aclist[P[src]].isEmpty()) {petree.add(aclist[P[src]].peekFirst(), 1);}} else {while (!walist[P[src]].isEmpty()) {int pos = walist[P[src]].pollLast();watree.set(pos, 0);petree.set(pos, 0);if (!aclist[P[src]].isEmpty()) {petree.add(aclist[P[src]].peekFirst(), -1);}}while (!aclist[P[src]].isEmpty()) {int pos = aclist[P[src]].pollLast();actree.set(pos, 0);}actree.set(src, 1);aclist[P[src]].addFirst(src);}while (p < Q && query[p][0] == src) {var qu = query[p];ans1[qu[2]] = actree.query(qu[0], qu[1] + 1);ans2[qu[2]] = watree.query(qu[0], qu[1] + 1) + petree.query(qu[0], qu[1] + 1);++p;}}PrintWriter pw = new PrintWriter(System.out);for (int i = 0; i < Q; ++i) {pw.println(ans1[i] + " " + ans2[i]);}pw.close();}static void tr(Object...objects) {System.out.println(Arrays.deepToString(objects));}}