Submission #993492
Source Code Expand
import java.io.*; import java.util.*; public class Main { FastScanner in; PrintWriter out; class Segment implements Comparable<Segment> { int from, to; int mul, add; public Segment(int from, int to, int mul, int add) { super(); this.from = from; this.to = to; this.mul = mul; this.add = add; } public int compareTo(Segment arg0) { return Integer.compare(from, arg0.from); } } void solve() { int n = in.nextInt(); int[] a = new int[n]; for (int i = 0; i + 1 < n; i++) { a[i] = in.nextInt(); } int m = in.nextInt(); ArrayList<Segment> cur = new ArrayList<Main.Segment>(); cur.add(new Segment(1, (int) 1e9, 1, 0)); for (int opPos = n - 3; opPos >= 1; opPos--) { ArrayList<Segment> next = new ArrayList<Main.Segment>(); for (Segment s : cur) { if (s.from > s.to) { throw new AssertionError(); } if (s.mul == 1) { if (s.from + s.add >= a[opPos + 1]) { s.add -= a[opPos + 1]; next.add(s); } else { if (s.to + s.add <= a[opPos + 1]) { s.mul = -1; s.add = a[opPos + 1] - s.add; next.add(s); } else { int nFrom = a[opPos + 1] - s.add; next.add(new Segment(nFrom, s.to, 1, s.add - a[opPos + 1])); s.to = nFrom - 1; s.mul = -1; s.add = a[opPos + 1] - s.add; next.add(s); } } } else { if (-s.to + s.add >= a[opPos + 1]) { s.add -= a[opPos + 1]; next.add(s); } else { if (-s.from + s.add <= a[opPos + 1]) { s.mul = 1; s.add = a[opPos + 1] - s.add; next.add(s); } else { int nFrom = -(a[opPos + 1] - s.add); next.add(new Segment(nFrom, s.to, 1, a[opPos + 1] - s.add)); s.to = nFrom - 1; s.add -= a[opPos + 1]; next.add(s); } } } } cur = next; } Collections.sort(cur); for (int i = 0; i < m; i++) { int val = in.nextInt(); int l = 0, r = cur.size(); while (r - l > 1) { int mid = (l + r) >> 1; if (cur.get(mid).from <= val) { l = mid; } else { r = mid; } } long ans = cur.get(l).add + cur.get(l).mul * val; out.println(a[0] - a[1] + ans); } } void run() { try { in = new FastScanner(new File("object.in")); out = new PrintWriter(new File("object.out")); solve(); out.close(); } catch (FileNotFoundException e) { e.printStackTrace(); } } void runIO() { in = new FastScanner(System.in); out = new PrintWriter(System.out); solve(); out.close(); } class FastScanner { BufferedReader br; StringTokenizer st; public FastScanner(File f) { try { br = new BufferedReader(new FileReader(f)); } catch (FileNotFoundException e) { e.printStackTrace(); } } public FastScanner(InputStream f) { br = new BufferedReader(new InputStreamReader(f)); } String next() { while (st == null || !st.hasMoreTokens()) { String s = null; try { s = br.readLine(); } catch (IOException e) { e.printStackTrace(); } if (s == null) return null; st = new StringTokenizer(s); } return st.nextToken(); } boolean hasMoreTokens() { while (st == null || !st.hasMoreTokens()) { String s = null; try { s = br.readLine(); } catch (IOException e) { e.printStackTrace(); } if (s == null) return false; st = new StringTokenizer(s); } return true; } int nextInt() { return Integer.parseInt(next()); } long nextLong() { return Long.parseLong(next()); } double nextDouble() { return Double.parseDouble(next()); } } public static void main(String[] args) { new Thread(null, new Runnable() { public void run() { new Main().runIO(); } }, "1", 1 << 26).start(); } }
Submission Info
Submission Time | |
---|---|
Task | H - Tokaido |
User | qwerty787788 |
Language | Java8 (OpenJDK 1.8.0) |
Score | 0 |
Code Size | 3987 Byte |
Status | WA |
Exec Time | 2120 ms |
Memory | 333784 KB |
Judge Result
Set Name | sample | dataset1 | dataset2 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 700 | 0 / 900 | ||||||||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
sample | sample-01.txt, sample-02.txt |
dataset1 | sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt |
dataset2 | sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01-01.txt | TLE | 2120 ms | 329468 KB |
01-02.txt | AC | 93 ms | 8532 KB |
01-03.txt | TLE | 2120 ms | 333784 KB |
01-04.txt | TLE | 2120 ms | 328608 KB |
01-05.txt | TLE | 2120 ms | 328792 KB |
01-06.txt | TLE | 2120 ms | 329488 KB |
01-07.txt | TLE | 2120 ms | 328892 KB |
01-08.txt | TLE | 2120 ms | 328204 KB |
01-09.txt | TLE | 2120 ms | 328092 KB |
01-10.txt | AC | 99 ms | 8532 KB |
01-11.txt | TLE | 2114 ms | 210448 KB |
01-12.txt | TLE | 2114 ms | 210228 KB |
01-13.txt | TLE | 2114 ms | 210040 KB |
01-14.txt | TLE | 2114 ms | 210172 KB |
01-15.txt | TLE | 2114 ms | 210500 KB |
01-16.txt | AC | 268 ms | 30648 KB |
01-17.txt | AC | 260 ms | 28976 KB |
01-18.txt | AC | 691 ms | 30240 KB |
01-19.txt | AC | 275 ms | 28772 KB |
02-01.txt | TLE | 2120 ms | 330656 KB |
02-02.txt | TLE | 2114 ms | 211432 KB |
02-03.txt | TLE | 2120 ms | 329268 KB |
02-04.txt | TLE | 2114 ms | 211980 KB |
02-05.txt | TLE | 2120 ms | 332564 KB |
02-06.txt | TLE | 2117 ms | 260256 KB |
02-07.txt | TLE | 2120 ms | 328672 KB |
02-08.txt | AC | 391 ms | 31964 KB |
02-09.txt | WA | 501 ms | 30816 KB |
02-10.txt | TLE | 2114 ms | 210144 KB |
02-11.txt | TLE | 2114 ms | 210824 KB |
02-12.txt | TLE | 2114 ms | 210456 KB |
02-13.txt | TLE | 2114 ms | 210544 KB |
02-14.txt | AC | 532 ms | 33432 KB |
02-15.txt | AC | 547 ms | 35048 KB |
02-16.txt | AC | 475 ms | 47240 KB |
sample-01.txt | AC | 97 ms | 8432 KB |
sample-02.txt | AC | 97 ms | 8428 KB |