技術室奥プログラミングコンテスト#2 E - 歩くNPCたち(Walking NPCs)
解法
解説:歩くNPCたち from 理玖 川崎
www.slideshare.net解説の通り、小さな v について v ごとに累積和を作っておき、大きな v については小さな t について t ごとに累積和を作れば良い。
コード
import java.io.IOException; import java.io.InputStream; import java.io.OutputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.NoSuchElementException; /* _ooOoo_ o8888888o 88" . "88 (| -_- |) O\ = /O ____/`---'\____ .' \\| |// `. / \\||| : |||// \ / _||||| -:- |||||- \ | | \\\ - /// | | | \_| ''\---/'' | | \ .-\__ `-` ___/-. / ___`. .' /--.--\ `. . __ ."" '< `.___\_<|>_/___.' >'"". | | : `- \`.;`\ _ /`;.`/ - ` : | | \ \ `-. \_ __\ /__ _/ .-` / / ======`-.____`-.___\_____/___.-`____.-'====== `=---=' ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ pass System Test! */ public class Main { private static class Task { void solve(FastScanner in, PrintWriter out) { final int BUCKET_SIZE = 317; ArrayList<int[]> fastMovers = new ArrayList<>(); ArrayList<Integer>[] X = new ArrayList[BUCKET_SIZE * 2 + 1]; for (int i = 0; i < X.length; i++) { X[i] = new ArrayList<>(); } int N = in.nextInt(); for (int i = 0; i < N; i++) { int x = in.nextInt(); int v = in.nextInt(); if (Math.abs(v) > BUCKET_SIZE) { fastMovers.add(new int[]{x, v}); } else { X[v + BUCKET_SIZE].add(x); } } int Q = in.nextInt(); ArrayList<int[]> queries = new ArrayList<>(Q); for (int i = 0; i < Q; i++) { int t = in.nextInt(); int l = in.nextInt(); int r = in.nextInt(); queries.add(new int[]{t, l, r, i}); } int[] ans = new int[Q]; int[] sum = new int[BUCKET_SIZE * BUCKET_SIZE]; for (int v = -BUCKET_SIZE; v <= BUCKET_SIZE; v++) { if (X[v + BUCKET_SIZE].isEmpty()) continue; Arrays.fill(sum, 0); for (int x : X[v + BUCKET_SIZE]) sum[x]++; for (int i = 1; i < sum.length; i++) sum[i] += sum[i - 1]; for (int[] query : queries) { int t = query[0]; int l = query[1]; int r = query[2]; int q = query[3]; int left = Math.max(l - v * t, 0); int right = Math.min(r - v * t, sum.length - 1); if (left > right) continue; ans[q] += sum[right]; if (left > 0) ans[q] -= sum[left - 1]; } } //クエリを時間でソート Collections.sort(queries, (o1, o2) -> Integer.compare(o1[0], o2[0])); //高速で動くNPCは速度の絶対値でソート Collections.sort(fastMovers, (o1, o2) -> Integer.compare(Math.abs(o1[1]), Math.abs(o2[1]))); int prevTime = -1; boolean imosUsed = true; for (int[] query : queries) { int t = query[0]; int l = query[1]; int r = query[2]; int q = query[3]; if (prevTime < t) { if (imosUsed) { Arrays.fill(sum, 0); imosUsed = false; } boolean updated = false; for (int[] npc : fastMovers) { int x = npc[0]; int v = npc[1]; long vt = (long) v * t; if (sum.length <= Math.abs(vt)) break; long pos = vt + x; if (pos < 0 || sum.length <= pos) continue; sum[(int) pos]++; updated = true; imosUsed = true; } if (updated) { for (int i = 1; i < sum.length; i++) { sum[i] += sum[i - 1]; } } prevTime = t; } ans[q] += sum[r]; if (l > 0) ans[q] -= sum[l - 1]; } for (int i = 0; i < Q; i++) { out.println(ans[i]); } } } /** * ここから下はテンプレートです。 */ public static void main(String[] args) { OutputStream outputStream = System.out; FastScanner in = new FastScanner(); PrintWriter out = new PrintWriter(outputStream); Task solver = new Task(); solver.solve(in, out); out.close(); } private static class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int bufferLength = 0; private boolean hasNextByte() { if (ptr < bufferLength) { return true; } else { ptr = 0; try { bufferLength = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (bufferLength <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; } boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } double nextDouble() { return Double.parseDouble(next()); } double[] nextDoubleArray(int n) { double[] array = new double[n]; for (int i = 0; i < n; i++) { array[i] = nextDouble(); } return array; } double[][] nextDoubleMap(int n, int m) { double[][] map = new double[n][]; for (int i = 0; i < n; i++) { map[i] = nextDoubleArray(m); } return map; } public int nextInt() { return (int) nextLong(); } public int[] nextIntArray(int n) { int[] array = new int[n]; for (int i = 0; i < n; i++) array[i] = nextInt(); return array; } public long[] nextLongArray(int n) { long[] array = new long[n]; for (int i = 0; i < n; i++) array[i] = nextLong(); return array; } public String[] nextStringArray(int n) { String[] array = new String[n]; for (int i = 0; i < n; i++) array[i] = next(); return array; } public char[][] nextCharMap(int n) { char[][] array = new char[n][]; for (int i = 0; i < n; i++) array[i] = next().toCharArray(); return array; } } }