Submission #1570792
Source Code Expand
// package arc.arc082; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.Comparator; import java.util.InputMismatchException; public class Main { public static void main(String[] args) { InputReader in = new InputReader(System.in); PrintWriter out = new PrintWriter(System.out); int X = in.nextInt(); int n = in.nextInt(); long[] k = new long[n+1]; for (int i = 0; i < n ; i++) { k[i] = in.nextInt(); } k[n] = 1000000000 + 100; int q = in.nextInt(); int[][] query = new int[q][3]; for (int i = 0; i < q; i++) { for (int j = 0; j < 2 ; j++) { query[i][j] = in.nextInt(); } query[i][2] = i; } Arrays.sort(query, Comparator.comparingInt(u -> u[0])); long[] answer = new long[q]; long[] min = new long[]{0, 0}; long[] max = new long[]{X, X}; int fr = 0; boolean dec = true; for (int i = 0; i <= n ; i++) { while (fr < q && query[fr][0] <= k[i]) { long since = query[fr][0] - (i == 0 ? 0 : k[i-1]); long last = 0; if (min[1] <= query[fr][1] && query[fr][1] <= max[1]) { last = min[0] + query[fr][1] - min[1]; } else if (query[fr][1] < min[1]) { last = min[0]; } else if (max[1] < query[fr][1]) { last = max[0]; } answer[query[fr][2]] = Math.max(0, Math.min(X, last + since * (dec ? -1 : 1))); fr++; } // upd long time = k[i] - (i == 0 ? 0 : k[i-1]); long toMin = min[0] + time * (dec ? -1 : 1); long toMax = max[0] + time * (dec ? -1 : 1); if (dec) { if (0 <= toMin && toMax <= X) { min[0] = toMin; max[0] = toMax; } else if (toMax >= 0) { min[0] = 0; max[0] = toMax; min[1] += Math.abs(toMin); } else { min[0] = max[0] = 0; } } else { if (0 <= toMin && toMax <= X) { min[0] = toMin; max[0] = toMax; } else if (toMin <= X) { min[0] = toMin; max[0] = X; max[1] -= Math.abs(toMax - X); } else { min[0] = max[0] = X; } } if (min[0] == max[0]) { min[1] = max[1] = -1; } dec = !dec; } for (int i = 0; i < q ; i++) { out.println(answer[i]); } out.flush(); } public static void debug(Object... o) { System.err.println(Arrays.deepToString(o)); } public static class InputReader { private static final int BUFFER_LENGTH = 1 << 12; private InputStream stream; private byte[] buf = new byte[BUFFER_LENGTH]; private int curChar; private int numChars; public InputReader(InputStream stream) { this.stream = stream; } private int next() { if (numChars == -1) { throw new InputMismatchException(); } if (curChar >= numChars) { curChar = 0; try { numChars = stream.read(buf); } catch (IOException e) { throw new InputMismatchException(); } if (numChars <= 0) return -1; } return buf[curChar++]; } public char nextChar() { return (char) skipWhileSpace(); } public String nextToken() { int c = skipWhileSpace(); StringBuilder res = new StringBuilder(); do { res.append((char) c); c = next(); } while (!isSpaceChar(c)); return res.toString(); } public int nextInt() { return (int) nextLong(); } public long nextLong() { int c = skipWhileSpace(); long sgn = 1; if (c == '-') { sgn = -1; c = next(); } long res = 0; do { if (c < '0' || c > '9') { throw new InputMismatchException(); } res *= 10; res += c - '0'; c = next(); } while (!isSpaceChar(c)); return res * sgn; } public double nextDouble() { return Double.valueOf(nextToken()); } int skipWhileSpace() { int c = next(); while (isSpaceChar(c)) { c = next(); } return c; } boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } } }
Submission Info
Submission Time | |
---|---|
Task | F - Sandglass |
User | hamadu |
Language | Java8 (OpenJDK 1.8.0) |
Score | 700 |
Code Size | 5431 Byte |
Status | AC |
Exec Time | 463 ms |
Memory | 38448 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 1_003.txt, 1_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 1_033.txt, 1_034.txt, 1_035.txt, 1_036.txt, 1_037.txt, 1_038.txt, 1_039.txt, 1_040.txt, 1_041.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 185 ms | 23892 KB |
0_001.txt | AC | 157 ms | 25940 KB |
0_002.txt | AC | 142 ms | 23120 KB |
1_003.txt | AC | 255 ms | 35452 KB |
1_004.txt | AC | 257 ms | 37236 KB |
1_005.txt | AC | 259 ms | 33412 KB |
1_006.txt | AC | 291 ms | 33592 KB |
1_007.txt | AC | 261 ms | 32692 KB |
1_008.txt | AC | 267 ms | 32828 KB |
1_009.txt | AC | 268 ms | 31776 KB |
1_010.txt | AC | 299 ms | 33124 KB |
1_011.txt | AC | 284 ms | 35928 KB |
1_012.txt | AC | 259 ms | 35012 KB |
1_013.txt | AC | 261 ms | 32144 KB |
1_014.txt | AC | 268 ms | 32584 KB |
1_015.txt | AC | 259 ms | 35124 KB |
1_016.txt | AC | 276 ms | 32504 KB |
1_017.txt | AC | 283 ms | 34692 KB |
1_018.txt | AC | 288 ms | 35172 KB |
1_019.txt | AC | 273 ms | 36824 KB |
1_020.txt | AC | 276 ms | 37512 KB |
1_021.txt | AC | 271 ms | 37364 KB |
1_022.txt | AC | 267 ms | 35680 KB |
1_023.txt | AC | 292 ms | 34948 KB |
1_024.txt | AC | 272 ms | 34848 KB |
1_025.txt | AC | 282 ms | 34740 KB |
1_026.txt | AC | 289 ms | 35328 KB |
1_027.txt | AC | 275 ms | 34512 KB |
1_028.txt | AC | 283 ms | 35288 KB |
1_029.txt | AC | 281 ms | 36736 KB |
1_030.txt | AC | 289 ms | 33644 KB |
1_031.txt | AC | 282 ms | 36336 KB |
1_032.txt | AC | 320 ms | 37852 KB |
1_033.txt | AC | 300 ms | 34704 KB |
1_034.txt | AC | 265 ms | 33188 KB |
1_035.txt | AC | 291 ms | 37044 KB |
1_036.txt | AC | 285 ms | 35532 KB |
1_037.txt | AC | 267 ms | 35148 KB |
1_038.txt | AC | 301 ms | 36932 KB |
1_039.txt | AC | 463 ms | 36008 KB |
1_040.txt | AC | 293 ms | 36644 KB |
1_041.txt | AC | 302 ms | 38448 KB |