結果
| 問題 | No.596 郵便配達 |
| ユーザー |
 37zigen
|
| 提出日時 | 2017-10-14 02:27:23 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 2,658 ms / 5,000 ms |
| コード長 | 5,269 bytes |
| コンパイル時間 | 2,014 ms |
| コンパイル使用メモリ | 81,684 KB |
| 実行使用メモリ | 419,508 KB |
| 最終ジャッジ日時 | 2024-11-17 14:21:47 |
| 合計ジャッジ時間 | 21,278 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 23 |
ソースコード
import java.io.FileNotFoundException;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Random;import java.util.Scanner;public class Main {public static void main(String[] args) throws FileNotFoundException {new Main().run();}void run() {Scanner sc = new Scanner(System.in);int MAX_ = sc.nextInt();if (!(1 <= MAX_ && MAX_ <= 1e7)) {throw new AssertionError();}int m = sc.nextInt();if (!(1 <= m && m <= 5 * 1e5)) {throw new AssertionError();}int[] x = new int[m];int[] d = new int[m];int[][] y = new int[m][];int sumd = 0;for (int i = 0; i < m; ++i) {x[i] = sc.nextInt();d[i] = sc.nextInt();if (!(d[i] > 0)) {throw new AssertionError();}if (!(0 <= x[i] && x[i] < MAX_))throw new AssertionError();sumd += d[i];y[i] = new int[d[i]];for (int j = 0; j < d[i]; ++j) {y[i][j] = sc.nextInt();if (!(0 <= y[i][j] && y[i][j] < MAX_))throw new AssertionError();}}if (!(1 <= sumd && sumd <= 1e6)) {throw new AssertionError();}System.out.println(solver(MAX_, m, x, d, y));}int MAX = 0;int INF = Integer.MAX_VALUE / 10;int solve(int[] l, int[] r) {int r1 = INF;int r2 = -INF;int l1 = INF;int l2 = -INF;// r1 -> r[r1]が最左// l1 <- (arg l=l1)が最左for (int i = 0; i < MAX; ++i) {if (r[i] != -1 && r1 == INF) {r1 = i;}if (l[i] != -1 && l1 == INF) {l1 = l[i];}}for (int i = MAX - 1; i >= 0; --i) {if (r[i] != -1 && r2 == -INF) {r2 = r[i];}if (l[i] != -1 && l2 == -INF) {l2 = i;}}for (int i = Math.min(l1, r1) + 1; i < Math.max(l2, r2); ++i) {if (l[i] == i) {l[i] = -1;}if (r[i] == i) {r[i] = -1;}}int[] arg_l = new int[MAX];Arrays.fill(arg_l, -1);for (int i = 0; i < l.length; ++i) {if (l[i] != -1) {arg_l[l[i]] = i;}}int[] middle = new int[MAX];for (int i = MAX - 1; i >= 0; --i) {if (l[i] != i && l[i] != -1) {++middle[i - 1];--middle[l[i]];}if (i + 1 < MAX) {middle[i] = middle[i + 1] + middle[i];}}int[][] s = new int[2][MAX];for (int i = 0; i < s.length; ++i) {for (int j = 0; j < s[i].length; ++j) {s[i][j] = INF;}}for (int i = Math.min(r1, l1); i <= Math.max(r2, l2); ++i) {if (r1 <= i && i < l1) {s[0][i] = i - r1;}if (l[i] == i || (middle[i] == 0 && l[i] == -1 && arg_l[i] == -1)) {// 何もなしs[0][i] = Math.min(s[0][i], 2 * Math.abs(i - Math.min(l1, r1)));if (i == 0) {s[1][i] = 0;s[0][i] = 0;} else {s[1][i] = Math.min(s[1][i], Math.min(s[1][i - 1] + 3, s[0][i - 1] + 1));s[0][i] = Math.min(s[0][i], Math.min(s[1][i - 1] + 3, s[0][i - 1] + 1));}} else if (l[i] != -1 && l[i] != i && arg_l[i] != -1 && arg_l[i] != i) {// 配達元かつ配達先s[1][i] = Math.min(s[1][i], s[1][i - 1] + 3);} else if (middle[i] > 0) {// 配達途中s[1][i] = Math.min(s[1][i], s[1][i - 1] + 3);} else if (arg_l[i] != -1 && i != 0) {// 配達先s[1][i] = Math.min(s[1][i], Math.min(s[0][i - 1] + 1, s[1][i - 1] + 3));} else if (l[i] != -1) {// 配達元s[1][i] = Math.min(s[1][i], s[1][i - 1] + 3);s[0][i] = Math.min(s[0][i], s[1][i - 1] + 3);s[0][i] = Math.min(s[0][i], 2 * Math.abs(i - Math.min(l1, r1)));} else {if (i == 0) {} elsethrow new AssertionError();}}int ans = 2 * (Math.max(l2, r2) - Math.min(l1, r1));for (int i = 0; i < MAX; ++i) {ans = Math.min(ans, s[0][i] + 2 * Math.abs(i - Math.max(l2, r2)) - (i == Math.max(l2, r2) ? 0 : 1));}return ans;}int solver(int MAX_, int m, int[] x, int[] d, int[][] y) {++MAX_;MAX = MAX_;int[] r = lr(MAX_, m, x, d, y)[1];int[] l = lr(MAX_, m, x, d, y)[0];int[] invl = new int[MAX];int[] invr = new int[MAX];Arrays.fill(invl, -1);Arrays.fill(invr, -1);for (int i = 0; i < MAX; ++i) {if (l[i] != -1) {int src = (MAX - 1) - i;int dst = (MAX - 1) - l[i];invr[src] = dst;}if (r[i] != -1) {int src = (MAX - 1) - i;int dst = (MAX - 1) - r[i];invl[src] = dst;}}return Math.max(0, Math.min(solve(l, r), solve(invl, invr)));}int[][] lr(int MAX_, int m, int[] x, int[] d, int[][] y) {MAX = MAX_;int[] r = new int[MAX];int[] l = new int[MAX];Arrays.fill(r, -1);Arrays.fill(l, -1);for (int i = 0; i < m; ++i) {int ma = r[x[i]] != -1 ? r[x[i]] : x[i] - 1;int mi = l[x[i]] != -1 ? l[x[i]] : x[i] + 1;for (int j = 0; j < d[i]; ++j) {ma = Math.max(ma, y[i][j]);mi = Math.min(mi, y[i][j]);}if (ma >= x[i]) {r[x[i]] = ma;}if (mi <= x[i]) {l[x[i]] = mi;}}{int ma = -1;for (int i = 0; i < MAX; ++i) {if (r[i] == -1)continue;if (ma < r[i]) {ma = r[i];} else if (ma >= r[i]) {r[i] = -1;}}}{int mi = MAX * 10;for (int i = MAX - 1; i >= 0; --i) {if (l[i] == -1)continue;if (mi > l[i]) {mi = l[i];} else if (mi <= l[i]) {l[i] = -1;}}}return new int[][] { l, r };}static void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}}