Submission #1159484
Source Code Expand
import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.SortedSet; import java.util.Set; import java.util.NavigableSet; import java.io.IOException; import java.io.InputStreamReader; import java.util.TreeSet; import java.util.StringTokenizer; import java.io.BufferedReader; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class Main { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); PrintWriter out = new PrintWriter(outputStream); TaskF solver = new TaskF(); solver.solve(1, in, out); out.close(); } static class TaskF { long period; public void solve(int testNumber, InputReader in, PrintWriter out) { int n = in.nextInt(); period = in.nextInt(); int[] a = new int[n]; int[] b = new int[n]; for (int i = 0; i < n; ++i) { a[i] = in.nextInt(); b[i] = in.nextInt(); } TreeSet<TaskF.ControlPoint> points = new TreeSet<>(); points.add(new TaskF.ControlPoint(0, 0)); long offset = 0; for (int i = 0; i < n; ++i) { if (i > 0) { offset = ((offset - a[i - 1] - a[i]) % period + period) % period; } if (b[i] == 1) { if (2 * a[i] > period) { out.println(-1); return; } int left = (int) ((offset - a[i] + period) % period); int right = (int) ((offset + a[i]) % period); TaskF.ControlPoint pl = ensurePoint(points, left); TaskF.ControlPoint pr = ensurePoint(points, right); if (pl.when < pr.when) { NavigableSet<TaskF.ControlPoint> after = points.tailSet(pl, false); while (!after.isEmpty() && after.first().when < pr.when) { points.remove(after.first()); } } else { NavigableSet<TaskF.ControlPoint> after = points.tailSet(pl, false); while (!after.isEmpty()) { points.remove(after.first()); } NavigableSet<TaskF.ControlPoint> before = points.headSet(pr, false); while (!before.isEmpty()) { points.remove(before.last()); } } long mid = 2L * a[i] - 1; if (!points.add(new TaskF.ControlPoint((int) ((left + mid) % period), pl.value + mid))) throw new RuntimeException(); } } long res = Long.MAX_VALUE; for (TaskF.ControlPoint p : points) { res = Math.min(res, p.value); } for (int i = 0; i < n; ++i) res += 2L * a[i]; out.println(res); } private TaskF.ControlPoint ensurePoint(TreeSet<TaskF.ControlPoint> points, int at) { TaskF.ControlPoint us = new TaskF.ControlPoint(at, 0); NavigableSet<TaskF.ControlPoint> tail = points.tailSet(us, true); TaskF.ControlPoint next = tail.isEmpty() ? points.first() : tail.first(); if (next.when == us.when) return next; NavigableSet<TaskF.ControlPoint> head = points.headSet(us, true); TaskF.ControlPoint prev = head.isEmpty() ? points.last() : head.last(); int dx = next.when - prev.when; if (dx < 0) dx += period; long dv = next.value - prev.value; if (dv != 0) { if (Math.abs(dx) != Math.abs(dv)) throw new RuntimeException(); long step = dv / dx; int odx = at - prev.when; if (odx < 0) odx += period; us.value = prev.value + odx * step; } else { us.value = prev.value; } points.add(us); return us; } static class ControlPoint implements Comparable<TaskF.ControlPoint> { int when; long value; public ControlPoint(int when, long value) { this.when = when; this.value = value; } public int compareTo(TaskF.ControlPoint o) { return when - o.when; } } } static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } public String next() { while (tokenizer == null || !tokenizer.hasMoreTokens()) { try { tokenizer = new StringTokenizer(reader.readLine()); } catch (IOException e) { throw new RuntimeException(e); } } return tokenizer.nextToken(); } public int nextInt() { return Integer.parseInt(next()); } } }
Submission Info
Submission Time | |
---|---|
Task | F - Train Service Planning |
User | Petr |
Language | Java8 (OpenJDK 1.8.0) |
Score | 1700 |
Code Size | 5668 Byte |
Status | AC |
Exec Time | 787 ms |
Memory | 71836 KB |
Judge Result
Set Name | Sample | All | subtask | subtask2 | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 700 / 700 | 500 / 500 | 500 / 500 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample1.txt, sample2.txt, sample3.txt, sample4.txt |
All | sample1.txt, sample2.txt, sample3.txt, sample4.txt, in1.txt, in10.txt, in101.txt, in102.txt, in103.txt, in104.txt, in105.txt, in106.txt, in107.txt, in108.txt, in109.txt, in11.txt, in110.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt, sample4.txt, sub2in1.txt, sub2in10.txt, sub2in11.txt, sub2in12.txt, sub2in13.txt, sub2in14.txt, sub2in15.txt, sub2in16.txt, sub2in17.txt, sub2in18.txt, sub2in19.txt, sub2in2.txt, sub2in20.txt, sub2in21.txt, sub2in22.txt, sub2in23.txt, sub2in24.txt, sub2in3.txt, sub2in4.txt, sub2in5.txt, sub2in6.txt, sub2in7.txt, sub2in8.txt, sub2in9.txt, subin1.txt, subin10.txt, subin101.txt, subin102.txt, subin103.txt, subin104.txt, subin105.txt, subin106.txt, subin107.txt, subin108.txt, subin109.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin20.txt, subin201.txt, subin21.txt, subin22.txt, subin23.txt, subin24.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt |
subtask | sample1.txt, sample2.txt, sample3.txt, subin1.txt, subin10.txt, subin101.txt, subin102.txt, subin103.txt, subin104.txt, subin105.txt, subin106.txt, subin107.txt, subin108.txt, subin109.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin20.txt, subin201.txt, subin21.txt, subin22.txt, subin23.txt, subin24.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt |
subtask2 | sample1.txt, sample2.txt, sample3.txt, sample4.txt, sub2in1.txt, sub2in10.txt, sub2in11.txt, sub2in12.txt, sub2in13.txt, sub2in14.txt, sub2in15.txt, sub2in16.txt, sub2in17.txt, sub2in18.txt, sub2in19.txt, sub2in2.txt, sub2in20.txt, sub2in21.txt, sub2in22.txt, sub2in23.txt, sub2in24.txt, sub2in3.txt, sub2in4.txt, sub2in5.txt, sub2in6.txt, sub2in7.txt, sub2in8.txt, sub2in9.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
in1.txt | AC | 121 ms | 21968 KB |
in10.txt | AC | 392 ms | 45332 KB |
in101.txt | AC | 435 ms | 48424 KB |
in102.txt | AC | 560 ms | 49824 KB |
in103.txt | AC | 479 ms | 49584 KB |
in104.txt | AC | 510 ms | 60988 KB |
in105.txt | AC | 462 ms | 51672 KB |
in106.txt | AC | 501 ms | 47048 KB |
in107.txt | AC | 474 ms | 54768 KB |
in108.txt | AC | 455 ms | 44152 KB |
in109.txt | AC | 567 ms | 59200 KB |
in11.txt | AC | 415 ms | 53076 KB |
in110.txt | AC | 443 ms | 53552 KB |
in12.txt | AC | 407 ms | 55180 KB |
in13.txt | AC | 424 ms | 48728 KB |
in14.txt | AC | 398 ms | 50692 KB |
in15.txt | AC | 440 ms | 55712 KB |
in16.txt | AC | 444 ms | 54764 KB |
in17.txt | AC | 426 ms | 55308 KB |
in18.txt | AC | 425 ms | 48764 KB |
in19.txt | AC | 436 ms | 52036 KB |
in2.txt | AC | 384 ms | 44816 KB |
in20.txt | AC | 432 ms | 57364 KB |
in21.txt | AC | 470 ms | 51536 KB |
in22.txt | AC | 453 ms | 50924 KB |
in23.txt | AC | 498 ms | 59112 KB |
in24.txt | AC | 461 ms | 48868 KB |
in25.txt | AC | 426 ms | 49120 KB |
in26.txt | AC | 382 ms | 48452 KB |
in27.txt | AC | 369 ms | 49000 KB |
in28.txt | AC | 407 ms | 48792 KB |
in3.txt | AC | 396 ms | 45356 KB |
in4.txt | AC | 406 ms | 48968 KB |
in5.txt | AC | 371 ms | 42996 KB |
in6.txt | AC | 435 ms | 54964 KB |
in7.txt | AC | 396 ms | 47552 KB |
in8.txt | AC | 351 ms | 42956 KB |
in9.txt | AC | 395 ms | 51224 KB |
sample1.txt | AC | 71 ms | 20052 KB |
sample2.txt | AC | 70 ms | 21076 KB |
sample3.txt | AC | 69 ms | 19412 KB |
sample4.txt | AC | 71 ms | 19668 KB |
sub2in1.txt | AC | 85 ms | 21076 KB |
sub2in10.txt | AC | 86 ms | 18388 KB |
sub2in11.txt | AC | 87 ms | 21716 KB |
sub2in12.txt | AC | 82 ms | 21716 KB |
sub2in13.txt | AC | 84 ms | 20564 KB |
sub2in14.txt | AC | 82 ms | 20820 KB |
sub2in15.txt | AC | 79 ms | 18772 KB |
sub2in16.txt | AC | 82 ms | 19924 KB |
sub2in17.txt | AC | 83 ms | 21588 KB |
sub2in18.txt | AC | 79 ms | 19668 KB |
sub2in19.txt | AC | 82 ms | 19668 KB |
sub2in2.txt | AC | 93 ms | 21588 KB |
sub2in20.txt | AC | 84 ms | 21588 KB |
sub2in21.txt | AC | 93 ms | 18388 KB |
sub2in22.txt | AC | 92 ms | 19412 KB |
sub2in23.txt | AC | 82 ms | 19668 KB |
sub2in24.txt | AC | 82 ms | 17492 KB |
sub2in3.txt | AC | 85 ms | 16596 KB |
sub2in4.txt | AC | 82 ms | 21716 KB |
sub2in5.txt | AC | 80 ms | 17236 KB |
sub2in6.txt | AC | 80 ms | 21588 KB |
sub2in7.txt | AC | 78 ms | 21460 KB |
sub2in8.txt | AC | 84 ms | 21588 KB |
sub2in9.txt | AC | 86 ms | 19668 KB |
subin1.txt | AC | 457 ms | 64860 KB |
subin10.txt | AC | 453 ms | 63800 KB |
subin101.txt | AC | 439 ms | 63716 KB |
subin102.txt | AC | 657 ms | 66896 KB |
subin103.txt | AC | 787 ms | 65180 KB |
subin104.txt | AC | 686 ms | 71284 KB |
subin105.txt | AC | 703 ms | 71704 KB |
subin106.txt | AC | 578 ms | 71836 KB |
subin107.txt | AC | 503 ms | 53752 KB |
subin108.txt | AC | 670 ms | 64460 KB |
subin109.txt | AC | 645 ms | 51100 KB |
subin11.txt | AC | 547 ms | 67396 KB |
subin12.txt | AC | 531 ms | 54296 KB |
subin13.txt | AC | 495 ms | 53612 KB |
subin14.txt | AC | 483 ms | 51220 KB |
subin15.txt | AC | 533 ms | 64716 KB |
subin16.txt | AC | 486 ms | 55580 KB |
subin17.txt | AC | 549 ms | 65584 KB |
subin18.txt | AC | 521 ms | 63908 KB |
subin19.txt | AC | 509 ms | 53252 KB |
subin2.txt | AC | 436 ms | 60864 KB |
subin20.txt | AC | 497 ms | 49428 KB |
subin201.txt | AC | 71 ms | 21460 KB |
subin21.txt | AC | 455 ms | 66576 KB |
subin22.txt | AC | 418 ms | 61524 KB |
subin23.txt | AC | 519 ms | 64812 KB |
subin24.txt | AC | 422 ms | 60932 KB |
subin3.txt | AC | 464 ms | 61800 KB |
subin4.txt | AC | 435 ms | 50388 KB |
subin5.txt | AC | 539 ms | 62784 KB |
subin6.txt | AC | 594 ms | 53076 KB |
subin7.txt | AC | 516 ms | 47412 KB |
subin8.txt | AC | 401 ms | 47940 KB |
subin9.txt | AC | 485 ms | 52952 KB |