#411505 (Java21) No.960 マンハッタン距離3

提出ソース

結果

問題	No.960 マンハッタン距離3
ユーザー	uwi
提出日時	2019-12-23 23:49:51
言語	Java21 (openjdk 21)
結果	AC
実行時間	1,001 ms / 2,000 ms
コード長	12,280 bytes
コンパイル時間	5,567 ms
コンパイル使用メモリ	90,296 KB
実行使用メモリ	80,460 KB
最終ジャッジ日時	2024-09-19 04:35:55
合計ジャッジ時間	56,206 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	53 ms 36,732 KB
testcase_01	AC	53 ms 36,580 KB
testcase_02	AC	52 ms 36,592 KB
testcase_03	AC	53 ms 36,716 KB
testcase_04	AC	53 ms 36,548 KB
testcase_05	AC	52 ms 36,916 KB
testcase_06	AC	52 ms 37,140 KB
testcase_07	AC	53 ms 36,820 KB
testcase_08	AC	52 ms 36,568 KB
testcase_09	AC	52 ms 36,888 KB
testcase_10	AC	52 ms 36,884 KB
testcase_11	AC	52 ms 36,928 KB
testcase_12	AC	52 ms 36,572 KB
testcase_13	AC	52 ms 36,928 KB
testcase_14	AC	53 ms 36,712 KB
testcase_15	AC	52 ms 37,056 KB
testcase_16	AC	52 ms 36,948 KB
testcase_17	AC	53 ms 36,864 KB
testcase_18	AC	54 ms 36,884 KB
testcase_19	AC	53 ms 36,936 KB
testcase_20	AC	57 ms 36,964 KB
testcase_21	AC	57 ms 37,096 KB
testcase_22	AC	54 ms 37,140 KB
testcase_23	AC	53 ms 36,896 KB
testcase_24	AC	52 ms 36,972 KB
testcase_25	AC	54 ms 37,264 KB
testcase_26	AC	53 ms 36,920 KB
testcase_27	AC	53 ms 36,860 KB
testcase_28	AC	52 ms 37,084 KB
testcase_29	AC	54 ms 36,700 KB
testcase_30	AC	54 ms 37,212 KB
testcase_31	AC	53 ms 36,836 KB
testcase_32	AC	53 ms 36,988 KB
testcase_33	AC	56 ms 37,096 KB
testcase_34	AC	55 ms 37,084 KB
testcase_35	AC	52 ms 36,864 KB
testcase_36	AC	54 ms 37,240 KB
testcase_37	AC	53 ms 36,944 KB
testcase_38	AC	52 ms 37,080 KB
testcase_39	AC	54 ms 36,908 KB
testcase_40	AC	54 ms 36,736 KB
testcase_41	AC	53 ms 37,032 KB
testcase_42	AC	53 ms 37,240 KB
testcase_43	AC	53 ms 37,044 KB
testcase_44	AC	53 ms 36,960 KB
testcase_45	AC	53 ms 36,896 KB
testcase_46	AC	53 ms 37,024 KB
testcase_47	AC	52 ms 37,128 KB
testcase_48	AC	54 ms 37,048 KB
testcase_49	AC	56 ms 36,736 KB
testcase_50	AC	55 ms 36,972 KB
testcase_51	AC	55 ms 37,060 KB
testcase_52	AC	56 ms 36,668 KB
testcase_53	AC	55 ms 37,032 KB
testcase_54	AC	53 ms 36,872 KB
testcase_55	AC	51 ms 36,920 KB
testcase_56	AC	55 ms 36,736 KB
testcase_57	AC	53 ms 37,140 KB
testcase_58	AC	52 ms 36,700 KB
testcase_59	AC	53 ms 36,888 KB
testcase_60	AC	56 ms 37,276 KB
testcase_61	AC	55 ms 37,188 KB
testcase_62	AC	57 ms 37,096 KB
testcase_63	AC	55 ms 37,060 KB
testcase_64	AC	56 ms 36,844 KB
testcase_65	AC	52 ms 36,668 KB
testcase_66	AC	52 ms 36,904 KB
testcase_67	AC	52 ms 36,712 KB
testcase_68	AC	54 ms 36,956 KB
testcase_69	AC	54 ms 36,724 KB
testcase_70	AC	53 ms 36,908 KB
testcase_71	AC	54 ms 37,036 KB
testcase_72	AC	54 ms 36,844 KB
testcase_73	AC	52 ms 37,060 KB
testcase_74	AC	53 ms 37,060 KB
testcase_75	AC	57 ms 36,600 KB
testcase_76	AC	53 ms 36,928 KB
testcase_77	AC	52 ms 37,096 KB
testcase_78	AC	53 ms 36,732 KB
testcase_79	AC	51 ms 36,684 KB
testcase_80	AC	53 ms 36,912 KB
testcase_81	AC	51 ms 36,804 KB
testcase_82	AC	51 ms 37,060 KB
testcase_83	AC	51 ms 36,876 KB
testcase_84	AC	50 ms 36,876 KB
testcase_85	AC	50 ms 36,912 KB
testcase_86	AC	50 ms 36,568 KB
testcase_87	AC	51 ms 36,968 KB
testcase_88	AC	53 ms 36,960 KB
testcase_89	AC	55 ms 36,832 KB
testcase_90	AC	52 ms 37,080 KB
testcase_91	AC	53 ms 36,600 KB
testcase_92	AC	52 ms 36,580 KB
testcase_93	AC	53 ms 36,860 KB
testcase_94	AC	52 ms 36,972 KB
testcase_95	AC	51 ms 37,008 KB
testcase_96	AC	52 ms 37,024 KB
testcase_97	AC	51 ms 36,916 KB
testcase_98	AC	50 ms 37,060 KB
testcase_99	AC	51 ms 36,896 KB
testcase_100	AC	52 ms 36,872 KB
testcase_101	AC	52 ms 36,928 KB
testcase_102	AC	51 ms 36,960 KB
testcase_103	AC	55 ms 36,900 KB
testcase_104	AC	52 ms 36,584 KB
testcase_105	AC	54 ms 36,904 KB
testcase_106	AC	53 ms 36,588 KB
testcase_107	AC	51 ms 36,896 KB
testcase_108	AC	51 ms 36,696 KB
testcase_109	AC	52 ms 36,736 KB
testcase_110	AC	51 ms 37,004 KB
testcase_111	AC	51 ms 36,944 KB
testcase_112	AC	51 ms 36,856 KB
testcase_113	AC	50 ms 36,568 KB
testcase_114	AC	51 ms 36,580 KB
testcase_115	AC	52 ms 36,704 KB
testcase_116	AC	52 ms 36,716 KB
testcase_117	AC	53 ms 36,592 KB
testcase_118	AC	51 ms 36,600 KB
testcase_119	AC	52 ms 36,904 KB
testcase_120	AC	55 ms 36,896 KB
testcase_121	AC	53 ms 36,888 KB
testcase_122	AC	50 ms 36,716 KB
testcase_123	AC	51 ms 36,968 KB
testcase_124	AC	51 ms 36,764 KB
testcase_125	AC	50 ms 36,588 KB
testcase_126	AC	51 ms 37,048 KB
testcase_127	AC	51 ms 36,864 KB
testcase_128	AC	305 ms 54,396 KB
testcase_129	AC	594 ms 75,640 KB
testcase_130	AC	535 ms 62,052 KB
testcase_131	AC	761 ms 78,556 KB
testcase_132	AC	951 ms 78,556 KB
testcase_133	AC	75 ms 38,572 KB
testcase_134	AC	128 ms 40,652 KB
testcase_135	AC	324 ms 56,020 KB
testcase_136	AC	322 ms 55,160 KB
testcase_137	AC	228 ms 55,004 KB
testcase_138	AC	670 ms 67,436 KB
testcase_139	AC	618 ms 74,592 KB
testcase_140	AC	267 ms 48,744 KB
testcase_141	AC	818 ms 79,692 KB
testcase_142	AC	411 ms 58,604 KB
testcase_143	AC	278 ms 57,648 KB
testcase_144	AC	688 ms 76,728 KB
testcase_145	AC	143 ms 41,124 KB
testcase_146	AC	251 ms 50,200 KB
testcase_147	AC	531 ms 66,832 KB
testcase_148	AC	384 ms 58,856 KB
testcase_149	AC	596 ms 70,552 KB
testcase_150	AC	708 ms 77,208 KB
testcase_151	AC	121 ms 40,724 KB
testcase_152	AC	234 ms 51,936 KB
testcase_153	AC	322 ms 59,940 KB
testcase_154	AC	102 ms 39,584 KB
testcase_155	AC	674 ms 75,480 KB
testcase_156	AC	308 ms 54,260 KB
testcase_157	AC	689 ms 75,752 KB
testcase_158	AC	668 ms 77,016 KB
testcase_159	AC	212 ms 49,996 KB
testcase_160	AC	119 ms 40,820 KB
testcase_161	AC	914 ms 76,672 KB
testcase_162	AC	261 ms 47,952 KB
testcase_163	AC	223 ms 54,776 KB
testcase_164	AC	951 ms 79,076 KB
testcase_165	AC	670 ms 75,372 KB
testcase_166	AC	210 ms 50,064 KB
testcase_167	AC	477 ms 60,400 KB
testcase_168	AC	365 ms 54,864 KB
testcase_169	AC	400 ms 58,428 KB
testcase_170	AC	335 ms 54,428 KB
testcase_171	AC	544 ms 62,104 KB
testcase_172	AC	414 ms 59,256 KB
testcase_173	AC	153 ms 42,100 KB
testcase_174	AC	705 ms 76,976 KB
testcase_175	AC	1,001 ms 80,460 KB
testcase_176	AC	669 ms 74,100 KB
testcase_177	AC	168 ms 44,824 KB
testcase_178	AC	658 ms 74,592 KB
testcase_179	AC	734 ms 76,656 KB
testcase_180	AC	242 ms 48,676 KB
testcase_181	AC	121 ms 40,152 KB
testcase_182	AC	152 ms 43,000 KB
testcase_183	AC	178 ms 44,808 KB
testcase_184	AC	156 ms 43,268 KB
testcase_185	AC	211 ms 46,516 KB
testcase_186	AC	229 ms 47,628 KB
testcase_187	AC	193 ms 45,604 KB
testcase_188	AC	53 ms 36,608 KB
testcase_189	AC	54 ms 36,848 KB
testcase_190	AC	57 ms 36,912 KB
testcase_191	AC	55 ms 36,604 KB
testcase_192	AC	57 ms 36,964 KB
testcase_193	AC	54 ms 36,592 KB
testcase_194	AC	56 ms 36,820 KB
testcase_195	AC	53 ms 36,732 KB
testcase_196	AC	538 ms 66,776 KB
testcase_197	AC	238 ms 50,100 KB
testcase_198	AC	450 ms 59,824 KB
testcase_199	AC	583 ms 73,984 KB
testcase_200	AC	230 ms 47,908 KB
testcase_201	AC	160 ms 43,388 KB
testcase_202	AC	597 ms 75,888 KB
testcase_203	AC	394 ms 59,300 KB
testcase_204	AC	763 ms 79,772 KB
testcase_205	AC	381 ms 59,532 KB
testcase_206	AC	349 ms 77,108 KB
testcase_207	AC	209 ms 46,884 KB
testcase_208	AC	630 ms 74,392 KB
testcase_209	AC	263 ms 54,140 KB
testcase_210	AC	165 ms 46,128 KB
testcase_211	AC	353 ms 58,068 KB
testcase_212	AC	168 ms 47,868 KB
testcase_213	AC	242 ms 58,656 KB
testcase_214	AC	840 ms 79,208 KB
testcase_215	AC	572 ms 77,076 KB
testcase_216	AC	841 ms 79,112 KB
testcase_217	AC	449 ms 62,380 KB
testcase_218	AC	255 ms 48,436 KB
testcase_219	AC	249 ms 58,980 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

package adv2019;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

public class D23_2 {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	int w, h;
	int[][] co;
	
	void solve()
	{
		w = ni();
		h = ni();
		int n = ni();
		co = new int[n][];
		for(int i = 0;i < n;i++){
			co[i] = new int[]{ni(), ni(), -1, -1};
			co[i][2] = co[i][0] + co[i][1];
			co[i][3] = co[i][0] - co[i][1];
		}
		Arrays.sort(co, new Comparator<int[]>() {
			public int compare(int[] a, int[] b) {
				return a[0] - b[0];
			}
		});
		
		int[][] es = new int[6*n][];
		int p = 0;
		for(int i = 1;i < n;i++){
			int d = Math.abs(co[i][0] - co[0][0]) + 
					Math.abs(co[i][1] - co[0][1]);
			if(d % 2 != 0){
				out.println(0);
				return;
			}
			
			//    c
			// ab/d
			// ----e
			// ih\f
			//    g
			
			if(co[0][0] == co[i][0]){
				if(co[0][1] < co[i][1]){
					// a
					es[p++] = new int[]{
							1, co[0][1] + d/2, co[0][1] + d/2 + 1, 1, 0, i
					};
					es[p++] = new int[]{
							w+1, co[0][1] + d/2, co[0][1] + d/2 + 1, -1, 0, i
					};
				}else{
					// i
					es[p++] = new int[]{
							1, co[0][1] - d/2, co[0][1] - d/2 + 1, 1, 0, i
					};
					es[p++] = new int[]{
							w+1, co[0][1] - d/2, co[0][1] - d/2 + 1, -1, 0, i
					};
				}
			}else{
				if(co[0][1] < co[i][1]){
					if(co[0][3] > co[i][3]){
						// b
						es[p++] = new int[]{
								1, co[0][1] + d/2, co[0][1] + d/2 + 1, 1, 0, i
						};
						es[p++] = new int[]{
								co[0][0], co[0][1] + d/2, co[0][1] + d/2 + 1, -1, 0, i
						};
						es[p++] = new int[]{
								co[0][0], co[0][1] + d/2, -1, 1, 2, i
						};
						es[p++] = new int[]{
								co[i][0], co[i][1] - d/2, -1, -1, 2, i
						};
						es[p++] = new int[]{
								co[i][0], co[i][1] - d/2, co[i][1] - d/2 + 1, 1, 0, i
						};
						es[p++] = new int[]{
								w+1, co[i][1] - d/2, co[i][1] - d/2 + 1, -1, 0, i
						};
					}else if(co[0][3] == co[i][3]){
						// c
						es[p++] = new int[]{
								1, co[i][1], h + 1, 1, 0, i
						};
						es[p++] = new int[]{
								co[0][0]+1, co[i][1], h + 1, -1, 0, i
						};
						es[p++] = new int[]{
								co[0][0]+1, co[i][1]-1, -1, 1, 2, i
						};
						es[p++] = new int[]{
								co[i][0], co[0][1], -1, -1, 2, i
						};
						es[p++] = new int[]{
								co[i][0], 1, co[0][1]+1, 1, 0, i
						};
						es[p++] = new int[]{
								w+1, 1, co[0][1]+1, -1, 0, i
						};
					}else{
						// d
						es[p++] = new int[]{
								co[i][0]-d/2, co[i][1], h + 1, 1, 0, i
						};
						es[p++] = new int[]{
								co[i][0]-d/2+1, co[i][1], h + 1, -1, 0, i
						};
						es[p++] = new int[]{
								co[i][0]-d/2+1, co[i][1]-1, -1, 1, 2, i
						};
						es[p++] = new int[]{
								co[0][0]+d/2, co[0][1], -1, -1, 2, i
						};
						es[p++] = new int[]{
								co[0][0]+d/2, 1, co[0][1]+1, 1, 0, i
						};
						es[p++] = new int[]{
								co[0][0]+d/2+1, 1, co[0][1]+1, -1, 0, i
						};
					}
				}else if(co[0][1] == co[i][1]){
					// e
					es[p++] = new int[]{
							co[0][0]+d/2, 1, h + 1, 1, 0, i
					};
					es[p++] = new int[]{
							co[0][0]+d/2+1, 1, h+1, -1, 0, i
					};
				}else if(co[0][1] > co[i][1]){
					if(co[0][2] > co[i][2]){
						// h
						es[p++] = new int[]{
								1, co[0][1] - d/2, co[0][1] - d/2 + 1, 1, 0, i
						};
						es[p++] = new int[]{
								co[0][0], co[0][1] - d/2, co[0][1] - d/2 + 1, -1, 0, i
						};
						es[p++] = new int[]{
								co[0][0], co[0][1] - d/2, 1, 1, 1, i
						};
						es[p++] = new int[]{
								co[i][0], co[i][1] + d/2, 1, -1, 1, i
						};
						es[p++] = new int[]{
								co[i][0], co[i][1] + d/2, co[i][1] + d/2 + 1, 1, 0, i
						};
						es[p++] = new int[]{
								w+1, co[i][1] + d/2, co[i][1] + d/2 + 1, -1, 0, i
						};
					}else if(co[0][2] == co[i][2]){
						// g
						es[p++] = new int[]{
								1, 1, co[i][1]+1, 1, 0, i
						};
						es[p++] = new int[]{
								co[0][0]+1, 1, co[i][1] + 1, -1, 0, i
						};
						es[p++] = new int[]{
								co[0][0]+1, co[i][1]+1, 1, 1, 1, i
						};
						es[p++] = new int[]{
								co[i][0], co[0][1], 1, -1, 1, i
						};
						es[p++] = new int[]{
								co[i][0], co[0][1], h+1, 1, 0, i
						};
						es[p++] = new int[]{
								w+1, co[0][1], h+1, -1, 0, i
						};
					}else{
						// f
						es[p++] = new int[]{
								co[i][0]-d/2, 1, co[i][1]+1, 1, 0, i
						};
						es[p++] = new int[]{
								co[i][0]-d/2+1, 1, co[i][1]+1, -1, 0, i
						};
						es[p++] = new int[]{
								co[i][0]-d/2+1, co[i][1]+1, 1, 1, 1, i
						};
						es[p++] = new int[]{
								co[0][0]+d/2, co[0][1], 1, -1, 1, i
						};
						es[p++] = new int[]{
								co[0][0]+d/2, co[0][1], h+1, 1, 0, i
						};
						es[p++] = new int[]{
								co[0][0]+d/2+1, co[0][1], h+1, -1, 0, i
						};
					}
				}
			}
		}
		es = Arrays.copyOf(es, p);
		Arrays.sort(es, new Comparator<int[]>() {
			public int compare(int[] a, int[] b) {
				return a[0] - b[0];
			}
		});
		
		MinHeap sups = new MinHeap(n);
		MinHeap infs = new MinHeap(n);
		long S02 = 0, S12 = 0, S22 = 0;
		long S01 = 0, S11 = 0, S21 = 0;
		int ins = 0;
		
		int x = 1;
		long S = 0;
		for(int[] e : es){
			if(x < e[0]){
				if(ins == n-1){
					boolean ok = true;
					if(S01 > 0){
						if(S11 % S01 == 0 && (S11/S01)*(S11/S01)*S01 == S21){
						}else{
							ok = false;
						}
					}
					if(S02 > 0){
						if(S12 % S02 == 0 && (S12/S02)*(S12/S02)*S02 == S22){
						}else{
							ok = false;
						}
					}
					
					if(ok){
//						tr(S01, S02, sups.size());
						if(S01 > 0 && S02 > 0){
							long ce1 = S11/S01;
							long ly1 = x+ce1;// y-x
							long ry1 = e[0]+ce1-1;

							long ce2 = S12/S02;
							long ly2 = ce2-x;// y+x
							long ry2 = ce2-e[0]+1;
							
							if((ly2-ly1) % 2 == 0 && ly1 <= ly2 && ry1 >= ry2){
								if(sups.size() == 0){
									S++;
								}else{
									long yy = (ly1+ly2)/2;
									long sup = sups.min();
									long inf = -infs.min();
									if(inf <= yy && yy < sup){
										S++;
									}
								}
							}
							
						}else if(S01 == 0 && S02 > 0){
							if(sups.size() == 0){
								S += e[0]-x;
							}else{
								long ce = S12/S02;
								long ly = ce-x+1;// y+x
								long ry = ce-e[0]+1;
								long sup = sups.min();
								long inf = -infs.min();
								inf = Math.max(inf, ry);
								sup = Math.min(sup, ly);
								S += Math.max(sup-inf, 0);
							}
						}else if(S02 == 0 && S01 > 0){
							if(sups.size() == 0){
								S += e[0]-x;
							}else{
								long ce = S11/S01;
								long ly = x+ce;// y-x
								long ry = e[0]+ce;
								long sup = sups.min();
								long inf = -infs.min();
								inf = Math.max(inf, ly);
								sup = Math.min(sup, ry);
								S += Math.max(sup-inf, 0);
							}
						}else{
							int sup = sups.min();
							int inf = -infs.min();
							if(inf < sup){
								S += (long)(sup-inf) * (e[0] - x);
							}
						}
//						tr(x, e[0], ins, n, S);
					}
				}
			}
			
			ins += e[3];
			if(e[4] == 0){
				// rectangle
				if(e[3] == 1){
					sups.add(e[5], e[2]);
					infs.add(e[5], -e[1]);
				}else{
					sups.remove(e[5]);
					infs.remove(e[5]);
				}
			}else if(e[4] == 1){
				// /
				S01 += e[3];
				S11 += e[3] * (e[1] - e[0]);
				S21 += (long)e[3] * (e[1] - e[0]) * (e[1] - e[0]);
			}else{
				// \
				S02 += e[3];
				S12 += e[3] * (e[1] + e[0]);
				S22 += (long)e[3] * (e[1] + e[0]) * (e[1] + e[0]);
			}
			x = e[0];
		}
		out.println(S);
	}
	
	public static class MinHeap {
		public int[] a;
		public int[] map;
		public int[] imap;
		public int n;
		public int pos;
		public static int INF = Integer.MAX_VALUE;
		
		public MinHeap(int m)
		{
			n = m+2;
			a = new int[n];
			map = new int[n];
			imap = new int[n];
			Arrays.fill(a, INF);
			Arrays.fill(map, -1);
			Arrays.fill(imap, -1);
			pos = 1;
		}
		
		public int add(int ind, int x)
		{
			int ret = imap[ind];
			if(imap[ind] < 0){
				a[pos] = x; map[pos] = ind; imap[ind] = pos;
				pos++;
				up(pos-1);
			}
			return ret != -1 ? a[ret] : x;
		}
		
		public int update(int ind, int x)
		{
			int ret = imap[ind];
			if(imap[ind] < 0){
				a[pos] = x; map[pos] = ind; imap[ind] = pos;
				pos++;
				up(pos-1);
			}else{
				int o = a[ret];
				a[ret] = x;
				up(ret);
				down(ret);
//				if(a[ret] > o){
//					up(ret);
//				}else{
//					down(ret);
//				}
			}
			return x;
		}
		
		public int remove(int ind)
		{
			if(pos == 1)return INF;
			if(imap[ind] == -1)return INF;
			
			pos--;
			int rem = imap[ind];
			int ret = a[rem];
			map[rem] = map[pos];
			imap[map[pos]] = rem;
			imap[ind] = -1;
			a[rem] = a[pos];
			a[pos] = INF;
			map[pos] = -1;
			
			up(rem);
			down(rem);
			return ret;
		}
		
		public int min() { return a[1]; }
		public int argmin() { return map[1]; }
		public int size() {	return pos-1; }
		
		private void up(int cur)
		{
			for(int c = cur, p = c>>>1;p >= 1 && a[p] > a[c];c>>>=1, p>>>=1){
				int d = a[p]; a[p] = a[c]; a[c] = d;
				int e = imap[map[p]]; imap[map[p]] = imap[map[c]]; imap[map[c]] = e;
				e = map[p]; map[p] = map[c]; map[c] = e;
			}
		}
		
		private void down(int cur)
		{
			for(int c = cur;2*c < pos;){
				int b = a[2*c] < a[2*c+1] ? 2*c : 2*c+1;
				if(a[b] < a[c]){
					int d = a[c]; a[c] = a[b]; a[b] = d;
					int e = imap[map[c]]; imap[map[c]] = imap[map[b]]; imap[map[b]] = e;
					e = map[c]; map[c] = map[b]; map[b] = e;
					c = b;
				}else{
					break;
				}
			}
		}
	}

	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//		Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
//			@Override
//			public void run() {
//				long s = System.currentTimeMillis();
//				solve();
//				out.flush();
//				if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//			}
//		};
//		t.start();
//		t.join();
	}
	
	public static void main(String[] args) throws Exception { new D23_2().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private 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 boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private 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 int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private long[] nal(int n)
	{
		long[] a = new long[n];
		for(int i = 0;i < n;i++)a[i] = nl();
		return a;
	}
	
	private 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 int[][] nmi(int n, int m) {
		int[][] map = new int[n][];
		for(int i = 0;i < n;i++)map[i] = na(m);
		return map;
	}
	
	private int ni() { return (int)nl(); }
	
	private 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) { System.out.println(Arrays.deepToString(o)); }
}

yukicoder

結果

テストケース

ソースコード