結果
| 問題 |
No.855 ヘビの日光浴
|
| コンテスト | |
| ユーザー |
 CuriousFairy315
|
| 提出日時 | 2019-07-09 22:25:56 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 48,110 bytes |
| コンパイル時間 | 4,318 ms |
| コンパイル使用メモリ | 105,160 KB |
| 実行使用メモリ | 83,112 KB |
| 最終ジャッジ日時 | 2024-10-01 20:43:59 |
| 合計ジャッジ時間 | 33,916 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 85 WA * 7 |
ソースコード
package yukicoder_2897;
import java.awt.Point;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.Serializable;
import java.lang.reflect.Array;
import java.util.AbstractCollection;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Locale;
import java.util.NoSuchElementException;
import java.util.TreeMap;
import java.util.function.Predicate;
public class Main {
public static void main(String[] args) {
new Main();
}
private static class Direction{
public static final int DOWN = 0, LEFT = 1, UP = 2, RIGHT = 3;
}
private final boolean DEBUG = false;
private class Snake{
private int direction;
private int point, length;
public Snake(int H, int W, int X, int Y, int L) {
if (!IntRange.closed(1, 1000000000).contains(L)) System.exit(1);
if (!IntRange.closed(1, W).contains(X)) {
if (!IntRange.closed(1, 1000000000).contains(Y))System.exit(1);
if (X == 0) {
direction = Direction.LEFT;
point = Y;
length = L;
} else if (X == W + 1) {
direction = Direction.RIGHT;
point = Y;
length = L;
} else System.exit(1);
} else {
if (!IntRange.closed(1, 1000000000).contains(X))System.exit(1);
if (Y == 0) {
direction = Direction.UP;
point = X;
length = L;
} else if (Y == H + 1) {
direction = Direction.DOWN;
point = X;
length = L;
} else System.exit(1);
}
}
public int getDirection() {
return direction;
}
public int getPoint() {
return point;
}
public int getLength() {
return length;
}
}
public Main() {
FastIO io = new FastIO();
int H = io.nextInt(), W = io.nextInt(), N = io.nextInt();
if (!IntRange.closed(1, 1000000000).contains(H)) System.exit(1);
if (!IntRange.closed(1, 1000000000).contains(W)) System.exit(1);
if (!IntRange.closed(1, 100000).contains(N)) System.exit(1);
if ((long) H * W <= 1000000 && (long)H * W * N <= 10000000) { // 愚直解のチェック
int[][] d = new int[4][Math.max(H, W) + 2];
long ans = 0;
query: for (int i = 0;i < N;++ i) {
if (DEBUG) {
io.print("*");
for (int n = 1;n <= W;++ n) io.print(" " + d[Direction.UP][n]);
io.println(" *");
for (int n = 1;n <= H;++ n) {
io.print(d[Direction.LEFT][n]);
io.print(" ");
for (int n2 = 0;n2 < W;++ n2) io.print(" ");
io.println(d[Direction.RIGHT][n]);
}
io.print("*");
for (int n = 1;n <= W;++ n) io.print(" " + d[Direction.DOWN][n]);
io.println(" *");
}
int X = io.nextInt(), Y = io.nextInt(), L = io.nextInt();
if (DEBUG) io.println("turn:" + i + " (" + X + "," + Y + ")" + L);
if (X == 0 || X == W + 1) {
if (X == 0) {
for (int x = d[Direction.LEFT][Y] + 1;x <= Math.min(W, d[Direction.LEFT][Y] + L);++ x) {
if (d[Direction.UP][x] >= Y) {
d[Direction.LEFT][Y] = 0;
d[Direction.UP][x] = 0;
continue query;
} else if (d[Direction.DOWN][x] > H - Y) {
d[Direction.LEFT][Y] = 0;
d[Direction.DOWN][x] = 0;
continue query;
}
}
d[Direction.LEFT][Y] += L;
} else {
for (int x = W - d[Direction.RIGHT][Y];x > Math.max(0, W - d[Direction.RIGHT][Y] - L);-- x) {
if (d[Direction.UP][x] >= Y) {
d[Direction.RIGHT][Y] = 0;
d[Direction.UP][x] = 0;
continue query;
} else if (d[Direction.DOWN][x] > H - Y) {
d[Direction.RIGHT][Y] = 0;
d[Direction.DOWN][x] = 0;
continue query;
}
}
d[Direction.RIGHT][Y] += L;
}
if (d[Direction.LEFT][Y] + d[Direction.RIGHT][Y] > W) {
d[Direction.LEFT][Y] = 0;
d[Direction.RIGHT][Y] = 0;
}
} else {
if (Y == 0) {
for (int y = d[Direction.UP][X] + 1;y <= Math.min(H, d[Direction.UP][X] + L);++ y) {
if (d[Direction.LEFT][y] >= X) {
d[Direction.UP][X] = 0;
d[Direction.LEFT][y] = 0;
continue query;
} else if (d[Direction.RIGHT][y] > W - X) {
d[Direction.UP][X] = 0;
d[Direction.RIGHT][y] = 0;
continue query;
}
}
d[Direction.UP][X] += L;
} else {
for (int y = H - d[Direction.DOWN][X];y > Math.max(0, H - d[Direction.DOWN][X] - L);-- y) {
if (d[Direction.LEFT][y] >= X) {
d[Direction.DOWN][X] = 0;
d[Direction.LEFT][y] = 0;
continue query;
} else if (d[Direction.RIGHT][y] > W - X) {
d[Direction.DOWN][X] = 0;
d[Direction.RIGHT][y] = 0;
continue query;
}
}
d[Direction.DOWN][X] += L;
}
if (d[Direction.UP][X] + d[Direction.DOWN][X] > H) {
d[Direction.UP][X] = 0;
d[Direction.DOWN][X] = 0;
}
}
}
if (DEBUG) {
io.print("*");
for (int n = 1;n <= W;++ n) io.print(" " + d[Direction.UP][n]);
io.println(" *");
for (int n = 1;n <= H;++ n) {
io.print(d[Direction.LEFT][n]);
io.print(" ");
for (int n2 = 0;n2 < W;++ n2) io.print(" ");
io.println(d[Direction.RIGHT][n]);
}
io.print("*");
for (int n = 1;n <= W;++ n) io.print(" " + d[Direction.DOWN][n]);
io.println(" *");
}
for (int[] i : d) for (int j : i) ans += j;
io.println(ans);
io.flush();
return;
}
Snake[] snake = new Snake[N];
ArrayList<Integer> comp = new ArrayList<>();
for (int i : IntRange.open(N)) {
snake[i] = new Snake(H, W, io.nextInt(), io.nextInt(), io.nextInt());
comp.add(snake[i].getPoint());
}
comp.add(0);
comp.add(1000000001);
CompressTree<Integer> compress = new CompressTree<>(comp);
CircularArray<SegmentTree<Integer>> segment = new CircularArray<>(4);
for (int d : IntRange.open(4)) {
segment.setFront(new SegmentTree<>(compress.size(), 0, (i, j) -> Math.max(i, j)));
segment.rotateNext();
}
for (int i : IntRange.open(N)) {
int index = compress.zip(snake[i].getPoint()), direction = snake[i].getDirection();
int sumLength = segment.get(direction).get(index) + snake[i].getLength();
int lenIndex = compress.floorZip(sumLength) + 1;
int left, right;
switch(direction) {
case Direction.UP:
left = segment.get(direction - 1).binarySearch(0, lenIndex, l -> l < snake[i].getPoint()) + 1;
right = segment.get(direction + 1).binarySearch(0, lenIndex, l -> l < W + 1 - snake[i].getPoint()) + 1;
if (left < right) {
segment.get(direction).update(0, index);
segment.get(direction - 1).update(0, left);
} else if (left > right) {
segment.get(direction).update(0, index);
segment.get(direction + 1).update(0, right);
} else if (segment.get(direction + 2).get(index) + sumLength > H) {
segment.get(direction + 2).update(0, index);
segment.get(direction).update(0, index);
} else {
segment.get(direction).update(sumLength, index);
}
break;
case Direction.LEFT:
left = segment.get(direction - 1).binarySearch(0, lenIndex, l -> l < H + 1 - snake[i].getPoint()) + 1;
right = segment.get(direction + 1).binarySearch(0, lenIndex, l -> l < snake[i].getPoint()) + 1;
if (left < right) {
segment.get(direction).update(0, index);
segment.get(direction - 1).update(0, left);
} else if (left > right) {
segment.get(direction).update(0, index);
segment.get(direction + 1).update(0, right);
} else if (segment.get(direction + 2).get(index) + sumLength > W) {
segment.get(direction + 2).update(0, index);
segment.get(direction).update(0, index);
} else {
segment.get(direction).update(sumLength, index);
}
break;
case Direction.DOWN:
lenIndex = compress.ceilingZip(H - sumLength) + 1;
left = segment.get(direction - 1).binarySearch(compress.size(), lenIndex, l -> l < W + 1 - snake[i].getPoint()) - 1;
right = segment.get(direction + 1).binarySearch(compress.size(), lenIndex, l -> l < snake[i].getPoint()) - 1;
if (left < right) {
segment.get(direction).update(0, index);
segment.get(direction + 1).update(0, right);
} else if (left > right) {
segment.get(direction).update(0, index);
segment.get(direction - 1).update(0, left);
} else if (segment.get(direction + 2).get(index) + sumLength > H) {
segment.get(direction + 2).update(0, index);
segment.get(direction).update(0, index);
} else {
segment.get(direction).update(sumLength, index);
}
break;
case Direction.RIGHT:
lenIndex = compress.ceilingZip(W - sumLength) + 1;
left = segment.get(direction - 1).binarySearch(compress.size(), lenIndex, l -> l < snake[i].getPoint()) - 1;
right = segment.get(direction + 1).binarySearch(compress.size(), lenIndex, l -> l < H + 1 - snake[i].getPoint()) - 1;
if (left < right) {
segment.get(direction).update(0, index);
segment.get(direction + 1).update(0, right);
} else if (left > right) {
segment.get(direction).update(0, index);
segment.get(direction - 1).update(0, left);
} else if (segment.get(direction + 2).get(index) + sumLength > W) {
segment.get(direction + 2).update(0, index);
segment.get(direction).update(0, index);
} else {
segment.get(direction).update(sumLength, index);
}
break;
}
if (DEBUG) {
io.print("turn:" + i + " snake:(");
switch(direction) {
case Direction.UP:
io.print(snake[i].getPoint() + ", 0)");
break;
case Direction.LEFT:
io.print("0, " + snake[i].getPoint() + ")");
break;
case Direction.RIGHT:
io.print((W + 1) + ", " + snake[i].getPoint() + ")");
break;
case Direction.DOWN:
io.print(snake[i].getPoint() + ", " + (H + 1) + ")");
break;
}
io.println(": " + snake[i].getLength());
io.print("*");
for (int n = 1;n <= W;++ n) io.print(" " + (compress.hasZip(n) ? segment.get(Direction.UP).get(compress.zip(n)) : 0));
io.println(" *");
for (int n = 1;n <= H;++ n) {
io.print("" + (compress.hasZip(n) ? segment.get(Direction.LEFT).get(compress.zip(n)) : 0));
io.print(" ");
for (int n2 = 0;n2 < W;++ n2) io.print(" ");
io.println("" + (compress.hasZip(n) ? segment.get(Direction.RIGHT).get(compress.zip(n)) : 0));
}
io.print("*");
for (int n = 1;n <= W;++ n) io.print(" " + (compress.hasZip(n) ? segment.get(Direction.DOWN).get(compress.zip(n)) : 0));
io.println(" *");
}
}
long ans = 0;
for (SegmentTree<Integer> i : segment) {
for (int j : i.get()) ans += j;
}
io.println(ans);
io.flush();
}
/**
* 端がもう片側の端と繋がり、循環する固定長配列を提供します。
* @author 31536000
*
* @param <T> 配列の型
*/
public class CircularArray<T> extends AbstractCollection<T> implements Serializable{
private static final long serialVersionUID = 4505120414119274426L;
final Object[] array;
int first = 0;
public CircularArray(int size) {
array = new Object[size];
}
public CircularArray(T[] array) {
this.array = array;
}
private int getIndex(int index) {
index -= first;
if (index >= array.length) index %= array.length;
else if (index < 0) index = array.length + index % array.length;
return index;
}
public void setFront(T value) {
array[first] = value;
}
public void set(int index, T value) {
array[getIndex(index)] = value;
}
public void setBack(T value) {
array[first == 0 ? array.length - 1 : first - 1] = value;
}
public T get(int index) {
@SuppressWarnings("unchecked")
T ret = (T)array[getIndex(index)];
return ret;
}
public T front() {
@SuppressWarnings("unchecked")
T ret = (T)array[first];
return ret;
}
public T back() {
@SuppressWarnings("unchecked")
T ret = (T)(first == 0 ? array[array.length - 1] : array[first - 1]);
return ret;
}
public void rotate(int rotate) {
first = getIndex(rotate);
}
public void rotateNext() {
if (++first >= array.length) first = 0;
}
public void rotatePrevious() {
if (--first < 0) first = array.length - 1;
}
private class Iter implements Iterator<T> {
private int index;
private int count;
Iter() {
index = first;
count = 0;
}
@Override
public boolean hasNext() {
return count < array.length;
}
@Override
public T next() {
@SuppressWarnings("unchecked")
T ret = (T)array[index];
if (++index >= array.length) index = 0;
++ count;
return ret;
}
}
@Override
public Iterator<T> iterator() {
return new Iter();
}
@Override
public int size() {
return array.length;
}
}
public interface SegmentTreeInterface<T, E> {
/**
* データを更新します。
* @param dat 更新するデータ
* @param index 更新する場所
*/
public void update(E dat, int index);
/**
* 区間[left, right)のデータを更新します。
* @param dat 更新するデータ
* @param left 更新する場所の左区間
* @param right 更新する場所の右区間
*/
public void update(E dat, int left, int right);
/**
* 全ての値を取得します。
* @return 現在の値
*/
public T[] get();
/**
* 指定した場所の値を取得します。
* @param index 取得したい場所
* @return その場所の値
*/
public T get(int index);
/**
* 指定した範囲の合計を取得します。
* @param left 範囲の左区間
* @param right 範囲の右区間
* @return 半開区間[left, right)の合計
*/
public T get(int left, int right);
public default int binarySearch(Predicate<T> f) {
return binarySearch(0, size(), f);
}
/**
* 指定した範囲で二分探索を行います。
* @param left 範囲の左区間
* @param f 単調性を持つ関数
* @return 半開区間[left, size)において関数fがtrueを返す最大の値(無ければleft-1)
*/
public default int binarySearch(int left, Predicate<T> f) {
return binarySearch(left, size(), f);
}
/**
* 指定した範囲で二分探索を行います。
* @param left 範囲の左区間
* @param right 範囲の右区間
* @param f 単調性を持つ関数
* @return 半開区間[left, right)において関数fがtrueを返す最大の値(無ければleft-1)<br>
* ただしleft>rightなら、半開区間[right, left)において関数fがtrueを返す最小の値(無ければleft)
*/
public int binarySearch(int left, int right, Predicate<T> f);
/**
* 要素数を返します。
* @return 要素数
*/
public int size();
}
/**
* セグメント木です。<br>
* １点更新をO(logN)、範囲取得をO(logN)でできるデータ構造です。
* @author 31536000
*
* @param <T> 更新及び範囲取得を行いたいクラス
*/
public class SegmentTree<T> implements SegmentTreeInterface<T, T>{
private Associative<T> semigroup; // 演算関数
private T dat[]; // データ
private int size;
/**
* セグメント木を構築します。
* @param dat 初期値
* @param semigroup 演算関数
*/
public SegmentTree(int N, T dat, Associative<T> semigroup) {
this.semigroup = semigroup;
@SuppressWarnings("unchecked")
T[] data = (T[]) new Object[N];
Arrays.fill(data, dat);
build(data);
}
/**
* セグメント木を構築します。
* @param dat 初期値
* @param semigroup 演算関数
*/
public SegmentTree(T[] dat, Associative<T> semigroup) {
this.semigroup = semigroup;
build(dat);
}
/**
* セグメント木を構築します。
* @param dat 初期値
* @throws ClassCastException 演算関数が定義されていなければ返す
*/
@SuppressWarnings("unchecked")
public SegmentTree(int N, T dat) throws ClassCastException {
this(N, dat, (Associative<T>) dat);
}
/**
* セグメント木を構築します。
* @param dat 初期値
* @throws ClassCastException 演算関数が定義されていなければ返す
*/
@SuppressWarnings("unchecked")
public SegmentTree(T dat[]) throws ClassCastException {
this(dat, (Associative<T>) dat[0]);
}
@SuppressWarnings("unchecked")
private void build(T dat[]) { // セグ木を配列として作成
size = dat.length;
this.dat = (T[])new Object[Integer.highestOneBit(dat.length) << 2]; // 要素数を超える最小の2冪*2
System.arraycopy(dat, 0, this.dat, this.dat.length >> 1, dat.length); // 最下段を埋める
for (int i = this.dat.length / 2 - 1; i > 0; --i)
this.dat[i] = operate(this.dat[i << 1], this.dat[i << 1 | 1]); // 最下段以外すべて、下から埋める
}
private T operate(T left, T right) { // 演算関数
if (right == null) return left; // 右がnullの可能性の方がはるかに高いので
else if (left == null) return right;
else return semigroup.operate(left, right);
}
@Override
public void update(T dat, int index) {
index |= this.dat.length >> 1;
this.dat[index] = dat;
for (int i = index >> 1; i > 0; i >>= 1) this.dat[i] = operate(this.dat[i << 1], this.dat[i << 1 | 1]);
}
@Override
public T[] get() {
@SuppressWarnings("unchecked")
T[] ret = (T[]) Array.newInstance(dat[size].getClass(), size);
System.arraycopy(dat, dat.length >> 1, ret, 0, size);
return ret;
}
@Override
public T get(int l, int r) {
T L = null, R = null;
l += dat.length >> 1;
r += dat.length >> 1;
while (l < r) {
if ((l & 1) != 0) L = operate(L, dat[l++]);
if ((r & 1) != 0) R = operate(dat[r ^ 1], R);
l >>= 1;
r >>= 1;
}
return operate(L, R);
}
@Override
public T get(int index) {
return dat[index | dat.length >> 1];
}
@Override
public int size() {
return size;
}
@Override
public void update(T dat, int left, int right) {
for (int i = left;i < right;++ i) update(dat, i);
}
private int revBinarySearch(int right, int left, Predicate<T> f) {
left += dat.length >>> 1;
right += dat.length >>> 1;
T last = null, next;
int i = 0;
while (left >>> i < right) {
if ((right & 1) == 0) { // 上がある
if (f.test(next = operate(dat[right], last))) { // このright全部を含むか
last = next;
-- right;
} else left = right << i; // 左辺を移動
} else {
right >>>= 1;
++ i;
}
}
while (i > 0) { // 今度は降下しながら見ていく
right = right << 1 | 1;
-- i;
if ((left >>> i & 1) == 0) {
if (f.test(next = operate( dat[right], last))) {
last = next;
-- right;
} else left = right << i;
}
};
return right - (dat.length >>> 1) + 1;
}
@Override
public int binarySearch(int left, int right, Predicate<T> f) {
if (left > right) return revBinarySearch(left - 1, right - 1, f);
left += dat.length >>> 1;
right += dat.length >>> 1;
T last = null, next;
int i = 0;
while (left < right >>> i) {
if ((left & 1) == 0) { // 上がある
left >>>= 1;
++ i;
} else {
if (f.test(next = operate(last, dat[left]))) { // このleft全部を含むか
last = next;
++ left;
} else right = (left + 1 << i) - 1; // 左辺を移動
}
}
while (i > 0) { // 今度は降下しながら見ていく
left <<= 1;
-- i;
if ((right >>> i & 1) != 0) {
if (f.test(next = operate(last, dat[left]))) {
last = next;
++ left;
} else right = (left + 1 << i) - 1;
}
};
return left - (dat.length >>> 1) - 1;
}
}
public interface Associative<T> {
public T operate(T left, T right);
}
/**
* 座標圧縮をするライブラリです。
* @author 31536000
*
* @param <T> 座標圧縮を行う型
*/
public class CompressTree<T extends Comparable<T>>{
private TreeMap<T, Integer> zip;
private Object[] unzip;
/**
* datを用いて座圧します。
* @param dat 座圧する値
*/
public CompressTree(T[] dat) {
Arrays.sort(dat);
zip = new TreeMap<T, Integer>();
List<T> unzip = new ArrayList<T>();
for (int i = 0, j = 0;i < dat.length;++ i) {
if (zip.put(dat[i], j++) != null) {
zip.put(dat[i], --j-1);
} else unzip.add(dat[i]);
}
this.unzip = unzip.toArray();
}
/**
* datを用いて座圧します。
* @param dat 座圧する値
*/
public CompressTree(List<T> dat) {
dat.sort(null);
Object[] dats = dat.toArray();
zip = new TreeMap<T, Integer>();
List<T> unzip = new ArrayList<T>();
for (int i = 0, j = 0;i < dats.length;++ i) {
@SuppressWarnings("unchecked")
T push = (T) dats[i];
if (zip.put(push, j++) != null) {
zip.put(push, --j-1);
} else unzip.add(push);
}
this.unzip = unzip.toArray();
}
public boolean hasZip(T dat) {
return zip.containsKey(dat);
}
/**
* 座圧した値を求めます。
* @param dat 座圧前の値
* @return 座圧後の値
*/
public int zip(T dat) {
return zip.get(dat);
}
/**
* 座圧した値を求めます。
* @param dat 座圧前の値
* @return 座圧後の値
*/
public int floorZip(T dat) {
return zip.floorEntry(dat).getValue();
}
/**
* 座圧した値を求めます。
* @param dat 座圧前の値
* @return 座圧後の値
*/
public int ceilingZip(T dat) {
return zip.ceilingEntry(dat).getValue();
}
/**
* 座圧前の値を求めます。
* @param index 座圧後の値
* @return 座圧前の値
*/
public T unzip(int index) {
@SuppressWarnings("unchecked")
T ret = (T)unzip[index];
return ret;
}
/**
* 要素数を求めます。
* @return ユニークな要素数
*/
public int size() {
return unzip.length;
}
}
public class FastIO {
private final InputStream in = System.in;
private final byte[] buffer = new byte[1024];
private int read = 0;
private int length = 0;
public final PrintWriter out = new PrintWriter(System.out, false);
public final PrintWriter err = new PrintWriter(System.err, false);
private boolean hasNextByte() {
if (read < length) return true;
read = 0;
try {
length = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return length > 0;
}
private int readByte() {
return hasNextByte() ? buffer[read++] : -1;
}
private boolean isPrintableChar(int c) {
return 33 <= c && c <= 126;
}
private boolean isNumber(int c) {
return '0' <= c && c <= '9';
}
public boolean hasNext() {
while (hasNextByte() && !isPrintableChar(buffer[read])) read++;
return hasNextByte();
}
public char nextChar() {
if (!hasNextByte()) throw new NoSuchElementException();
return (char)readByte();
}
public char[][] nextChar(int height) {
char[][] ret = new char[height][];
for (int i = 0;i < ret.length;++ i) ret[i] = next().toCharArray();
return ret;
}
public String next() {
if (!hasNext()) throw new NoSuchElementException();
StringBuilder sb = new StringBuilder();
int b;
while (isPrintableChar(b = readByte())) sb.appendCodePoint(b);
return sb.toString();
}
public long nextLong() {
if (!hasNext()) throw new NoSuchElementException();
long n = 0;
boolean minus = false;
int b = readByte();
if (b == '-') {
minus = true;
b = readByte();
}
if (!isNumber(b)) throw new NumberFormatException();
while (true) {
if (isNumber(b)) {
n *= 10;
n += b - '0';
} else if (b == -1 || !isPrintableChar(b)) return minus ? -n : n;
else throw new NumberFormatException();
b = readByte();
}
}
public int nextInt() {
long nl = nextLong();
if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
return (int) nl;
}
public double nextDouble() {
return Double.parseDouble(next());
}
public int[] nextInt(int width) {
int[] ret = new int[width];
for (int i = 0;i < width;++ i) ret[i] = nextInt();
return ret;
}
public long[] nextLong(int width) {
long[] ret = new long[width];
for (int i = 0;i < width;++ i) ret[i] = nextLong();
return ret;
}
public int[][] nextInt(int width, int height) {
int[][] ret = new int[height][width];
for (int i = 0, j;i < height;++ i) for (j = 0;j < width;++ j) ret[i][j] = nextInt();
return ret;
}
public long[][] nextLong(int width, int height) {
long[][] ret = new long[height][width];
for (int i = 0, j;i < height;++ i) for (j = 0;j < width;++ j) ret[j][i] = nextLong();
return ret;
}
public boolean[] nextBoolean(char T) {
char[] s = next().toCharArray();
boolean[] ret = new boolean[s.length];
for (int i = 0;i < ret.length;++ i) ret[i] = s[i] == T;
return ret;
}
public boolean[][] nextBoolean(char T, int height) {
boolean[][] ret = new boolean[height][];
for (int i = 0;i < ret.length;++ i) {
char[] s = next().toCharArray();
ret[i] = new boolean[s.length];
for (int j = 0;j < ret[i].length;++ j) ret[i][j] = s[j] == T;
}
return ret;
}
public Point nextPoint() {
return new Point(nextInt(), nextInt());
}
public Point[] nextPoint(int width) {
Point[] ret = new Point[width];
for (int i = 0;i < width;++ i) ret[i] = nextPoint();
return ret;
}
@Override
protected void finalize() throws Throwable {
try {
super.finalize();
} finally {
in.close();
out.close();
err.close();
}
}
public void print(boolean b) {
out.print(b);
}
public void print(char c) {
out.print(c);
}
public void print(char[] s) {
out.print(s);
}
public void print(double d) {
out.print(d);
}
public void print(double d, int length) {
if (d < 0) {
out.print('-');
d = -d;
}
d += Math.pow(10, -length) / 2;
out.print((long)d);
out.print('.');
d -= (long)d;
for (int i = 0;i < length;++ i) {
d *= 10;
out.print((int)d);
d -= (int)d;
}
}
public void print(float f) {
out.print(f);
}
public void print(int i) {
out.print(i);
}
public void print(long l) {
out.print(l);
}
public void print(Object obj) {
out.print(obj);
}
public void print(String s) {
out.print(s);
}
public void print(Object[] obj, String perse) {
print(obj[0]);
for (int i = 1;i < obj.length;++ i) {
print(perse);
print(obj[i]);
}
}
public void print(Object[][] obj, String perse1, String perse2) {
print(obj[0], perse1);
for (int i = 1;i < obj.length;++ i) {
print(perse2);
print(obj[i], perse1);
}
}
public void printf(String format, Object... args) {
out.printf(format, args);
}
public void printf(Locale l, String format, Object... args) {
out.printf(l, format, args);
}
public void println() {
out.println();
}
public void println(boolean b) {
out.println(b);
}
public void println(char c) {
out.println(c);
}
public void println(char[] s) {
out.println(s);
}
public void println(double d) {
out.println(d);
}
public void println(double d, int length) {
print(d, length);
println();
}
public void println(float f) {
out.println(f);
}
public void println(int i) {
out.println(i);
}
public void println(long l) {
out.println(l);
}
public void println(Object obj) {
out.println(obj);
}
public void println(String s) {
out.println(s);
}
public void println(Object[] obj, String perse) {
print(obj, perse);
println();
}
public void println(Object[][] obj, String perse1, String perse2) {
print(obj, perse1, perse2);
println();
}
public void flush() {
out.flush();
err.flush();
}
}
public enum BoundType {
CLOSED, OPEN;
}
public static class Range<C> implements Serializable{
private static final long serialVersionUID = -4702828934863023392L;
protected C lower;
protected C upper;
protected BoundType lowerType;
protected BoundType upperType;
private Comparator<? super C> comparator;
protected Range(C lower, BoundType lowerType, C upper, BoundType upperType) {
this(lower, lowerType, upper, upperType, null);
}
protected Range(C lower, BoundType lowerType, C upper, BoundType upperType, Comparator<? super C> comparator) {
this.lower = lower;
this.upper = upper;
this.lowerType = lowerType;
this.upperType = upperType;
this.comparator = comparator;
}
public static <C extends Comparable<? super C>> Range<C> range(C lower, BoundType lowerType, C upper, BoundType upperType) {
if (lower != null && upper != null) {
int comp = lower.compareTo(upper);
if (comp > 0) return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED);
else if (comp == 0 && (lowerType == BoundType.OPEN || upperType == BoundType.OPEN))return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED);
}
return new Range<C>(lower, lowerType, upper, upperType);
}
public static <C> Range<C> range(C lower, BoundType lowerType, C upper, BoundType upperType, Comparator<? super C> comparator) {
if (lower != null && upper != null) {
int comp = comparator.compare(lower, upper);
if (comp > 0) return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, comparator);
else if (comp == 0 && (lowerType == BoundType.OPEN || upperType == BoundType.OPEN)) return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, comparator);
}
return new Range<C>(lower, lowerType, upper, upperType, comparator);
}
public static <C extends Comparable<? super C>> Range<C> all() {
return range(null, BoundType.OPEN, null, BoundType.OPEN);
}
public static <C> Range<C> all(Comparator<? super C> comparator) {
return range(null, BoundType.OPEN, null, BoundType.OPEN, comparator);
}
public static <C extends Comparable<? super C>> Range<C> atMost(C upper) {
return range(null, BoundType.OPEN, upper, BoundType.CLOSED);
}
public static <C> Range<C> atMost(C upper, Comparator<? super C> comparator) {
return range(null, BoundType.OPEN, upper, BoundType.CLOSED, comparator);
}
public static <C extends Comparable<? super C>> Range<C> lessThan(C upper) {
return range(null, BoundType.OPEN, upper, BoundType.OPEN);
}
public static <C> Range<C> lessThan(C upper, Comparator<? super C> comparator) {
return range(null, BoundType.OPEN, upper, BoundType.OPEN, comparator);
}
public static <C extends Comparable<? super C>> Range<C> downTo(C upper, BoundType boundType) {
return range(null, BoundType.OPEN, upper, boundType);
}
public static <C> Range<C> downTo(C upper, BoundType boundType, Comparator<? super C> comparator) {
return range(null, BoundType.OPEN, upper, boundType, comparator);
}
public static <C extends Comparable<? super C>> Range<C> atLeast(C lower) {
return range(lower, BoundType.CLOSED, null, BoundType.OPEN);
}
public static <C> Range<C> atLeast(C lower, Comparator<? super C> comparator) {
return range(lower, BoundType.CLOSED, null, BoundType.OPEN, comparator);
}
public static <C extends Comparable<? super C>> Range<C> greaterThan(C lower) {
return range(lower, BoundType.OPEN, null, BoundType.OPEN);
}
public static <C> Range<C> greaterThan(C lower, Comparator<? super C> comparator) {
return range(lower, BoundType.OPEN, null, BoundType.OPEN, comparator);
}
public static <C extends Comparable<? super C>> Range<C> upTo(C lower, BoundType boundType) {
return range(lower, boundType, null, BoundType.OPEN);
}
public static <C> Range<C> upTo(C lower, BoundType boundType, Comparator<? super C> comparator) {
return range(lower, boundType, null, BoundType.OPEN, comparator );
}
public static <C extends Comparable<? super C>> Range<C> open(C lower, C upper) {
return range(lower, BoundType.OPEN, upper, BoundType.OPEN);
}
public static <C> Range<C> open(C lower, C upper, Comparator<? super C> comparator) {
return range(lower, BoundType.OPEN, upper, BoundType.OPEN, comparator);
}
public static <C extends Comparable<? super C>> Range<C> openClosed(C lower, C upper) {
return range(lower, BoundType.OPEN, upper, BoundType.CLOSED);
}
public static <C> Range<C> openClosed(C lower, C upper, Comparator<? super C> comparator) {
return range(lower, BoundType.OPEN, upper, BoundType.CLOSED, comparator);
}
public static <C extends Comparable<? super C>> Range<C> closedOpen(C lower, C upper) {
return range(lower, BoundType.CLOSED, upper, BoundType.OPEN);
}
public static <C> Range<C> closedOpen(C lower, C upper, Comparator<? super C> comparator) {
return range(lower, BoundType.CLOSED, upper, BoundType.OPEN, comparator);
}
public static <C extends Comparable<? super C>> Range<C> closed(C lower, C upper) {
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
}
public static <C> Range<C> closed(C lower, C upper, Comparator<? super C> comparator) {
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED, comparator);
}
public static <C extends Comparable<? super C>> Range<C> singleton(C value) {
return range(value, BoundType.CLOSED, value, BoundType.CLOSED);
}
public static <C> Range<C> singleton(C value, Comparator<? super C> comparator) {
return range(value, BoundType.CLOSED, value, BoundType.CLOSED, comparator);
}
public static <C extends Comparable<? super C>> Range<C> empty() {
return range(null, BoundType.CLOSED, null, BoundType.CLOSED);
}
public static <C> Range<C> empty(Comparator<? super C> comparator) {
return range(null, BoundType.CLOSED, null, BoundType.CLOSED, comparator);
}
public static <C extends Comparable<? super C>> Range<C> encloseAll(Iterable<C> values) {
C lower = values.iterator().next();
C upper = lower;
for (C i : values) {
if (lower.compareTo(i) > 0) lower = i;
if (upper.compareTo(i) < 0) upper = i;
}
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
}
public static <C> Range<C> encloseAll(Iterable<C> values, Comparator<? super C> comparator) {
C lower = values.iterator().next();
C upper = lower;
for (C i : values) {
if (comparator.compare(lower, i) > 0) lower = i;
if (comparator.compare(upper, i) < 0) upper = i;
}
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED, comparator);
}
protected int compareLower(C value) {
return compareLower(value, BoundType.CLOSED);
}
protected int compareLower(C value, BoundType boundType) {
return compareLower(lower, lowerType, value, boundType);
}
protected int compareLower(C lower, BoundType lowerType, C value) {
return compareLower(lower, lowerType, value, BoundType.CLOSED);
}
protected int compareLower(C lower, BoundType lowerType, C value, BoundType boundType) {
if (lower == null) return value == null ? 0 : -1;
else if (value == null) return 1;
int compare;
if (comparator == null) {
@SuppressWarnings("unchecked")
Comparable<C> comp = (Comparable<C>)lower;
compare = comp.compareTo(value);
} else compare = comparator.compare(lower, value);
if (compare == 0) {
if (lowerType == BoundType.CLOSED) -- compare;
if (boundType == BoundType.CLOSED) ++ compare;
}
return compare;
}
protected int compareUpper(C value) {
return compareUpper(value, BoundType.CLOSED);
}
protected int compareUpper(C value, BoundType boundType) {
return compareUpper(upper, upperType, value, boundType);
}
protected int compareUpper(C upper, BoundType upperType, C value) {
return compareUpper(upper, upperType, value, BoundType.CLOSED);
}
protected int compareUpper(C upper, BoundType upperType, C value, BoundType boundType) {
if (upper == null) return value == null ? 0 : 1;
if (value == null) return -1;
int compare;
if (comparator == null) {
@SuppressWarnings("unchecked")
Comparable<C> comp = (Comparable<C>)upper;
compare = comp.compareTo(value);
} else compare = comparator.compare(upper, value);
if (compare == 0) {
if (upperType == BoundType.CLOSED) ++ compare;
if (boundType == BoundType.CLOSED) -- compare;
}
return compare;
}
public boolean hasLowerBound() {
return lower != null;
}
public C lowerEndpoint() {
if (hasLowerBound()) return lower;
throw new IllegalStateException();
}
public BoundType lowerBoundType() {
if (hasLowerBound()) return lowerType;
throw new IllegalStateException();
}
public boolean hasUpperBound() {
return upper != null;
}
public C upperEndpoint() {
if (hasUpperBound()) return upper;
throw new IllegalStateException();
}
public BoundType upperBoundType() {
if (hasUpperBound()) return upperType;
throw new IllegalStateException();
}
/**
* この区間が空集合か判定します。
* @return 空集合ならばtrue
*/
public boolean isEmpty() {
return lower == null && upper == null && lowerType == BoundType.CLOSED;
}
/**
* 与えられた引数が区間の左側に位置するか判定します。<br>
* 接する場合は区間の左側ではないと判定します。
* @param value 調べる引数
* @return 区間の左側に位置するならtrue
*/
public boolean isLess(C value) {
return isLess(value, BoundType.CLOSED);
}
protected boolean isLess(C value, BoundType boundType) {
return compareLower(value, boundType) > 0;
}
/**
* 与えられた引数が区間の右側に位置するか判定します。<br>
* 接する場合は区間の右側ではないと判定します。
* @param value 調べる引数
* @return 区間の右側に位置するならtrue
*/
public boolean isGreater(C value) {
return isGreater(value, BoundType.CLOSED);
}
private boolean isGreater(C value, BoundType boundType) {
return compareUpper(value, boundType) < 0;
}
/**
* 与えられた引数が区間内に位置するか判定します。<br>
* 接する場合も区間内に位置すると判定します。
* @param value 調べる引数
* @return 区間内に位置するならtrue
*/
public boolean contains(C value) {
return !isLess(value) && !isGreater(value) && !isEmpty();
}
/**
* 与えられた引数すべてが区間内に位置するか判定します。<br>
* 接する場合も区間内に位置すると判定します。
* @param value 調べる要素
* @return 全ての要素が区間内に位置するならtrue
*/
public boolean containsAll(Iterable<? extends C> values) {
for (C i : values) if (!contains(i)) return false;
return true;
}
/**
* 与えられた区間がこの区間に内包されるか判定します。<br>
*
* @param other
* @return 与えられた区間がこの区間に内包されるならtrue
*/
public boolean encloses(Range<C> other) {
return !isLess(other.lower, other.lowerType) && !isGreater(other.upper, other.upperType);
}
/**
* 与えられた区間がこの区間と公差するか判定します。<br>
* 接する場合は公差するものとします。
* @param value 調べる引数
* @return 区間が交差するならtrue
*/
public boolean isConnected(Range<C> other) {
if (this.isEmpty() || other.isEmpty()) return false;
C lower, upper;
BoundType lowerType, upperType;
if (isLess(other.lower, other.lowerType)) {
lower = other.lower;
lowerType = other.lowerType;
} else {
lower = this.lower;
lowerType = this.lowerType;
}
if (isGreater(other.upper, other.upperType)) {
upper = other.upper;
upperType = other.upperType;
} else {
upper = this.upper;
upperType = this.upperType;
}
if (lower == null || upper == null) return true;
int comp = compareLower(lower, lowerType, upper, upperType);
return comp <= 0;
}
/**
* この区間との積集合を返します。
* @param connectedRange 積集合を求める区間
* @return 積集合
*/
public Range<C> intersection(Range<C> connectedRange) {
if (this.isEmpty() || connectedRange.isEmpty()) {
if (comparator == null) return new Range<C>(null, BoundType.CLOSED, null, BoundType.CLOSED);
return empty(comparator);
}
C lower, upper;
BoundType lowerType, upperType;
if (isLess(connectedRange.lower, connectedRange.lowerType)) {
lower = connectedRange.lower;
lowerType = connectedRange.lowerType;
} else {
lower = this.lower;
lowerType = this.lowerType;
}
if (isGreater(connectedRange.upper, connectedRange.upperType)) {
upper = connectedRange.upper;
upperType = connectedRange.upperType;
} else {
upper = this.upper;
upperType = this.upperType;
}
if (comparator == null) {
return new Range<C>(lower, lowerType, upper, upperType);
}
return range(lower, lowerType, upper, upperType, comparator);
}
/**
* この区間との和集合を返します。
* @param other 和集合を求める区間
* @return 和集合
*/
public Range<C> span(Range<C> other) {
if (other.isEmpty()) return new Range<C>(lower, lowerType, upper, upperType);
C lower, upper;
BoundType lowerType, upperType;
if (isLess(other.lower, other.lowerType)) {
lower = this.lower;
lowerType = this.lowerType;
} else {
lower = other.lower;
lowerType = other.lowerType;
}
if (isGreater(other.upper, other.upperType)) {
upper = this.upper;
upperType = this.upperType;
} else {
upper = other.upper;
upperType = other.upperType;
}
return new Range<C>(lower, lowerType, upper, upperType, comparator);
}
@Override
public boolean equals(Object object) {
if (this == object) return true;
if (object instanceof Range) {
@SuppressWarnings("unchecked")
Range<C> comp = (Range<C>) object;
return compareLower(comp.lower, comp.lowerType) == 0 && compareUpper(comp.upper, comp.upperType) == 0 && lowerType == comp.lowerType && upperType == comp.upperType;
}
return false;
}
@Override
public int hashCode() {
if (lower == null && upper == null) return 0;
else if (lower == null) return upper.hashCode();
else if (upper == null) return lower.hashCode();
return lower.hashCode() ^ upper.hashCode();
}
@Override
public String toString() {
if (isEmpty()) return "()";
return (lowerType == BoundType.OPEN ? "(" : "[") + (lower == null ? "" : lower.toString()) + ".." + (upper == null ? "" : upper.toString()) + (upperType == BoundType.OPEN ? ")" : "]");
}
}
public interface IterableFunction<T> {
public T next(T value);
}
public static class IterableRange<C> extends Range<C> implements Iterable<C>{
private static final long serialVersionUID = 9065915259748260688L;
protected IterableFunction<C> func;
protected IterableRange(C lower, BoundType lowerType, C upper, BoundType upperType, IterableFunction<C> func) {
super(lower, lowerType, upper, upperType);
this.func = func;
}
public static <C extends Comparable<? super C>> IterableRange<C> range(C lower, BoundType lowerType, C upper, BoundType upperType, IterableFunction<C> func) {
if (lower == null || upper == null) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
int comp = lower.compareTo(upper);
if (comp > 0) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
else if (comp == 0 && (lowerType == BoundType.OPEN || upperType == BoundType.OPEN)) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
return new IterableRange<C>(lower, lowerType, upper, upperType, func);
}
public static <C extends Comparable<? super C>> IterableRange<C> open(C lower, C upper, IterableFunction<C> func) {
if (lower == null) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
return range(func.next(lower), BoundType.CLOSED, upper, BoundType.OPEN, func);
}
public static <C extends Comparable<? super C>> IterableRange<C> openClosed(C lower, C upper, IterableFunction<C> func) {
if (lower == null) return new IterableRange<C>(null, BoundType.CLOSED, null, BoundType.CLOSED, func);
return range(func.next(lower), BoundType.CLOSED, upper, BoundType.CLOSED, func);
}
public static <C extends Comparable<? super C>> IterableRange<C> closedOpen(C lower, C upper, IterableFunction<C> func) {
return range(lower, BoundType.CLOSED, upper, BoundType.OPEN, func);
}
public static <C extends Comparable<? super C>> IterableRange<C> closed(C lower, C upper, IterableFunction<C> func) {
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED, func);
}
public static <C extends Comparable<? super C>> IterableRange<C> singleton(C value, IterableFunction<C> func) {
return range(value, BoundType.CLOSED, value, BoundType.CLOSED, func);
}
private class Iter implements Iterator<C> {
C now;
Iter() {
now = lower;
}
@Override
public final boolean hasNext() {
return !isGreater(now);
}
@Override
public final C next() {
C ret = now;
now = func.next(now);
return ret;
}
@Override
public final void remove() {
throw new UnsupportedOperationException();
}
}
@Override
public Iterator<C> iterator() {
return new Iter();
}
public int getDistance() {
C check = upper;
int ret = 0;
while (lower != check) {
check = func.next(check);
++ ret;
}
return ret;
}
}
public static class IntRange extends IterableRange<Integer>{
private static final long serialVersionUID = 8177932312110314067L;
private static class Next implements IterableFunction<Integer> {
@Override
public Integer next(Integer value) {
return value + 1;
}
}
protected IntRange() {
super(null, BoundType.CLOSED, null, BoundType.CLOSED, new Next());
}
protected IntRange(int lower, BoundType lowerType, int upper, BoundType upperType) {
super(lower, lowerType, upper, upperType, new Next());
}
public static IntRange range(int lower, BoundType lowerType, int upper, BoundType upperType) {
if (lower > upper) return new IntRange();
if (lowerType == BoundType.OPEN) ++ lower;
if (upperType == BoundType.OPEN) -- upper;
return new IntRange(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
}
public static IntRange open(int lower, int upper) {
return range(lower, BoundType.OPEN, upper, BoundType.OPEN);
}
public static IntRange open(int upper) {
return range(0, BoundType.CLOSED, upper, BoundType.OPEN);
}
public static IntRange openClosed(int lower, int upper) {
return range(lower, BoundType.OPEN, upper, BoundType.CLOSED);
}
public static IntRange closedOpen(int lower, int upper) {
return range(lower, BoundType.CLOSED, upper, BoundType.OPEN);
}
public static IntRange closed(int lower, int upper) {
return range(lower, BoundType.CLOSED, upper, BoundType.CLOSED);
}
public static IntRange closed(int upper) {
return range(0, BoundType.CLOSED, upper, BoundType.CLOSED);
}
public static IntRange singleton(int value) {
return range(value, BoundType.CLOSED, value, BoundType.CLOSED);
}
private class Iter implements Iterator<Integer> {
int now;
public Iter() {
now = lower;
}
@Override
public final boolean hasNext() {
return now <= upper;
}
@Override
public final Integer next() {
return now++;
}
@Override
public final void remove() {
throw new UnsupportedOperationException();
}
}
@Override
public Iterator<Integer> iterator() {
return new Iter();
}
@Override
public int getDistance() {
int ret = upper - lower;
if (upperType == BoundType.CLOSED) ++ ret;
return ret;
}
public int getClosedLower() {
return lower;
}
public int getOpenLower() {
return lower - 1;
}
public int getClosedUpper() {
return upperType == BoundType.CLOSED ? upper : upper - 1;
}
public int getOpenUpper() {
return upperType == BoundType.CLOSED ? upper + 1 : upper;
}
}
}