Submission #1561164
Source Code Expand
import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class Main { static InputStream is; static PrintWriter out; static String INPUT = ""; static void solve() { int X = ni(); int K = ni(); int[] r = new int[K+1]; for(int i = 0;i < K;i++){ r[i+1] = ni(); } int[] infs = new int[K+1]; int[] sups = new int[K+1]; int[] bases = new int[K+1]; infs[0] = 0; sups[0] = X; bases[0] = 0; for(int i = 1;i < K+1;i++){ int t = r[i] - r[i-1]; int dir = i&1; // 1:down, 0:up if(dir == 1){ int nb = bases[i-1] - t; if(nb >= 0){ infs[i] = infs[i-1]; sups[i] = sups[i-1]; bases[i] = nb; }else{ infs[i] = infs[i-1] - nb; sups[i] = sups[i-1]; if(infs[i] >= sups[i]){ sups[i] = infs[i]; } bases[i] = 0; } }else{ int nb = bases[i-1] + t; if((long)nb + sups[i-1] - infs[i-1] <= X){ infs[i] = infs[i-1]; sups[i] = sups[i-1]; bases[i] = nb; }else{ infs[i] = infs[i-1]; sups[i] = sups[i-1] - ((sups[i-1] - infs[i-1]+nb)-X); if(infs[i] >= sups[i]){ sups[i] = infs[i]; } bases[i] = X - (sups[i] - infs[i]); } } } StringBuilder sb = new StringBuilder(); for(int Q = ni();Q > 0;Q--){ int t = ni(), a = ni(); int ind = Arrays.binarySearch(r, t); if(ind < 0)ind = -ind-2; int w = 0; if(a <= infs[ind]){ w = bases[ind]; }else if(a >= sups[ind]){ w = bases[ind] + (sups[ind] - infs[ind]); }else{ w = bases[ind] + (a - infs[ind]); } if((ind & 1) == 0){ // down w -= t - r[ind]; if(w < 0)w = 0; }else{ w += t - r[ind]; if(w > X)w = X; } sb.append(w).append("\n"); } out.print(sb); } public static void main(String[] args) throws Exception { long S = System.currentTimeMillis(); is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); solve(); out.flush(); long G = System.currentTimeMillis(); tr(G-S+"ms"); } private static boolean eof() { if(lenbuf == -1)return true; int lptr = ptrbuf; while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false; try { is.mark(1000); while(true){ int b = is.read(); if(b == -1){ is.reset(); return true; }else if(!isSpaceChar(b)){ is.reset(); return false; } } } catch (IOException e) { return true; } } private static byte[] inbuf = new byte[1024]; static int lenbuf = 0, ptrbuf = 0; private static int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } // private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); } private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private static double nd() { return Double.parseDouble(ns()); } private static char nc() { return (char)skip(); } private static String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private static char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private static char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private static int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private static int ni() { int num = 0, b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); } }
Submission Info
Submission Time | |
---|---|
Task | F - Sandglass |
User | uwi |
Language | Java8 (OpenJDK 1.8.0) |
Score | 700 |
Code Size | 5029 Byte |
Status | AC |
Exec Time | 182 ms |
Memory | 36776 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 | 66 ms | 19412 KB |
0_001.txt | AC | 67 ms | 16852 KB |
0_002.txt | AC | 69 ms | 21204 KB |
1_003.txt | AC | 145 ms | 24620 KB |
1_004.txt | AC | 147 ms | 25408 KB |
1_005.txt | AC | 139 ms | 27432 KB |
1_006.txt | AC | 153 ms | 23724 KB |
1_007.txt | AC | 150 ms | 25620 KB |
1_008.txt | AC | 153 ms | 28412 KB |
1_009.txt | AC | 135 ms | 24856 KB |
1_010.txt | AC | 143 ms | 24488 KB |
1_011.txt | AC | 155 ms | 27696 KB |
1_012.txt | AC | 150 ms | 25516 KB |
1_013.txt | AC | 163 ms | 27968 KB |
1_014.txt | AC | 158 ms | 28400 KB |
1_015.txt | AC | 160 ms | 28000 KB |
1_016.txt | AC | 155 ms | 27408 KB |
1_017.txt | AC | 159 ms | 27896 KB |
1_018.txt | AC | 167 ms | 29700 KB |
1_019.txt | AC | 160 ms | 29944 KB |
1_020.txt | AC | 164 ms | 28496 KB |
1_021.txt | AC | 159 ms | 27392 KB |
1_022.txt | AC | 165 ms | 33224 KB |
1_023.txt | AC | 176 ms | 36776 KB |
1_024.txt | AC | 166 ms | 28164 KB |
1_025.txt | AC | 169 ms | 30012 KB |
1_026.txt | AC | 181 ms | 33580 KB |
1_027.txt | AC | 162 ms | 29636 KB |
1_028.txt | AC | 161 ms | 29156 KB |
1_029.txt | AC | 182 ms | 33812 KB |
1_030.txt | AC | 166 ms | 29476 KB |
1_031.txt | AC | 170 ms | 32280 KB |
1_032.txt | AC | 176 ms | 33404 KB |
1_033.txt | AC | 149 ms | 30032 KB |
1_034.txt | AC | 152 ms | 29056 KB |
1_035.txt | AC | 168 ms | 32592 KB |
1_036.txt | AC | 154 ms | 29744 KB |
1_037.txt | AC | 156 ms | 27540 KB |
1_038.txt | AC | 176 ms | 34720 KB |
1_039.txt | AC | 149 ms | 24208 KB |
1_040.txt | AC | 166 ms | 32980 KB |
1_041.txt | AC | 176 ms | 34972 KB |