結果

問題 No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ
コンテスト
ユーザー ks2m
提出日時 2024-02-23 22:13:05
言語 Java
(openjdk 23)
結果
TLE  
実行時間 -
コード長 2,322 bytes
コンパイル時間 4,430 ms
コンパイル使用メモリ 81,096 KB
実行使用メモリ 51,536 KB
最終ジャッジ日時 2024-09-29 06:56:56
合計ジャッジ時間 14,082 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.PriorityQueue;
import java.util.function.IntConsumer;

public class Main {
	static int val;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		PrintWriter pw = new PrintWriter(System.out);
		for (int z = 0; z < t; z++) {
			String[] sa = br.readLine().split(" ");
			int n = Integer.parseInt(sa[0]);
//			int l = Integer.parseInt(sa[1]);
			int[] x = new int[n];
			int[] y = new int[n];
			for (int i = 0; i < n; i++) {
				sa = br.readLine().split(" ");
				x[i] = Integer.parseInt(sa[0]);
				y[i] = Integer.parseInt(sa[1]);
			}

			Mo mo = new Mo(n, x, y,
					i -> {
						val++;
					},
					i -> {
						val--;
					});
			pw.println(n);
			for (Mo.Query o : mo.arr) {
				pw.println(o.l + " " + o.r);
			}
		}
		pw.flush();
		br.close();
	}

	static class Mo {
		int q, d;
		Query[] arr;

		/**
		 * クエリ処理（l, rは半開区間）
		 * 
		 * @param n
		 * @param l 左側（含む）（0≦l＜n）
		 * @param r 右側（含まない）（0＜r≦n）
		 * @param add 該当indexの要素を追加する処理
		 * @param del 該当indexの要素を削除する処理
		 */
		public Mo(int n, int[] l, int[] r, IntConsumer add, IntConsumer del) {
			q = l.length;
			d = Math.max(1, (int) (n / Math.max(1.0, Math.sqrt(q / 1.5))));
			arr = new Query[q];
			for (int i = 0; i < q; i++) {
				Query o = new Query();
				o.l = l[i];
				o.r = r[i];
				o.l2 = o.l / d;
				arr[i] = o;
			}

			PriorityQueue<Query> que = new PriorityQueue<>((o1, o2) -> {
				if (o1.l2 != o2.l2) {
					return o1.l2 - o2.l2;
				}
				if (o1.l2 % 2 == 0) {
					return o1.r - o2.r;
				} else {
					return o2.r - o1.r;
				}
			});
			for (Query o : arr) {
				que.add(o);
			}

			int il = 0;
			int ir = 0;
			while (!que.isEmpty()) {
				Query o = que.poll();
				while (il > o.l) {
					il--;
					add.accept(il);
				}
				while (ir < o.r) {
					add.accept(ir);
					ir++;
				}
				while (il < o.l) {
					del.accept(il);
					il++;
				}
				while (ir > o.r) {
					ir--;
					del.accept(ir);
				}
				o.ans = val;
			}
		}

		class Query {
			int l, r, l2, ans;
		}
	}
}
0