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

提出ソース

結果

問題	No.960 マンハッタン距離3
ユーザー	uwi
提出日時	2019-12-23 23:49:51
言語	Java21 (openjdk 21)
結果	AC
実行時間	1,007 ms / 2,000 ms
コード長	12,280 bytes
コンパイル時間	6,011 ms
コンパイル使用メモリ	90,588 KB
実行使用メモリ	95,168 KB
最終ジャッジ日時	2023-10-19 08:20:49
合計ジャッジ時間	55,602 ms
ジャッジサーバーID （参考情報）	judge13 / judge11

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	57 ms 52,584 KB
testcase_01	AC	56 ms 53,568 KB
testcase_02	AC	55 ms 53,568 KB
testcase_03	AC	56 ms 53,504 KB
testcase_04	AC	56 ms 53,560 KB
testcase_05	AC	56 ms 53,568 KB
testcase_06	AC	56 ms 52,464 KB
testcase_07	AC	56 ms 53,572 KB
testcase_08	AC	55 ms 52,364 KB
testcase_09	AC	55 ms 53,484 KB
testcase_10	AC	57 ms 53,560 KB
testcase_11	AC	56 ms 52,356 KB
testcase_12	AC	60 ms 52,352 KB
testcase_13	AC	57 ms 53,564 KB
testcase_14	AC	57 ms 53,568 KB
testcase_15	AC	56 ms 53,508 KB
testcase_16	AC	55 ms 52,364 KB
testcase_17	AC	56 ms 52,436 KB
testcase_18	AC	55 ms 53,576 KB
testcase_19	AC	55 ms 52,828 KB
testcase_20	AC	59 ms 53,588 KB
testcase_21	AC	59 ms 53,580 KB
testcase_22	AC	57 ms 53,568 KB
testcase_23	AC	57 ms 53,572 KB
testcase_24	AC	58 ms 52,448 KB
testcase_25	AC	57 ms 53,600 KB
testcase_26	AC	58 ms 53,484 KB
testcase_27	AC	59 ms 53,572 KB
testcase_28	AC	59 ms 53,576 KB
testcase_29	AC	57 ms 53,508 KB
testcase_30	AC	59 ms 52,636 KB
testcase_31	AC	58 ms 53,572 KB
testcase_32	AC	56 ms 53,492 KB
testcase_33	AC	60 ms 53,572 KB
testcase_34	AC	60 ms 53,580 KB
testcase_35	AC	58 ms 53,504 KB
testcase_36	AC	59 ms 53,596 KB
testcase_37	AC	57 ms 53,564 KB
testcase_38	AC	57 ms 53,568 KB
testcase_39	AC	59 ms 53,568 KB
testcase_40	AC	60 ms 52,460 KB
testcase_41	AC	61 ms 52,444 KB
testcase_42	AC	59 ms 52,592 KB
testcase_43	AC	59 ms 53,580 KB
testcase_44	AC	58 ms 53,520 KB
testcase_45	AC	58 ms 52,520 KB
testcase_46	AC	58 ms 53,572 KB
testcase_47	AC	59 ms 52,452 KB
testcase_48	AC	60 ms 52,460 KB
testcase_49	AC	60 ms 53,584 KB
testcase_50	AC	59 ms 53,572 KB
testcase_51	AC	60 ms 53,568 KB
testcase_52	AC	60 ms 53,576 KB
testcase_53	AC	60 ms 52,608 KB
testcase_54	AC	59 ms 53,492 KB
testcase_55	AC	59 ms 53,508 KB
testcase_56	AC	61 ms 53,580 KB
testcase_57	AC	60 ms 53,572 KB
testcase_58	AC	62 ms 52,604 KB
testcase_59	AC	59 ms 53,568 KB
testcase_60	AC	64 ms 52,596 KB
testcase_61	AC	66 ms 52,424 KB
testcase_62	AC	64 ms 53,592 KB
testcase_63	AC	61 ms 53,572 KB
testcase_64	AC	61 ms 52,608 KB
testcase_65	AC	62 ms 52,432 KB
testcase_66	AC	61 ms 53,572 KB
testcase_67	AC	58 ms 52,452 KB
testcase_68	AC	59 ms 52,576 KB
testcase_69	AC	59 ms 52,456 KB
testcase_70	AC	62 ms 52,604 KB
testcase_71	AC	61 ms 53,572 KB
testcase_72	AC	59 ms 53,516 KB
testcase_73	AC	58 ms 52,384 KB
testcase_74	AC	58 ms 53,504 KB
testcase_75	AC	59 ms 52,384 KB
testcase_76	AC	57 ms 53,492 KB
testcase_77	AC	59 ms 53,500 KB
testcase_78	AC	60 ms 53,504 KB
testcase_79	AC	57 ms 52,364 KB
testcase_80	AC	58 ms 52,456 KB
testcase_81	AC	58 ms 53,568 KB
testcase_82	AC	57 ms 52,376 KB
testcase_83	AC	58 ms 53,504 KB
testcase_84	AC	58 ms 53,492 KB
testcase_85	AC	60 ms 53,496 KB
testcase_86	AC	58 ms 52,500 KB
testcase_87	AC	58 ms 53,580 KB
testcase_88	AC	60 ms 52,608 KB
testcase_89	AC	60 ms 53,564 KB
testcase_90	AC	59 ms 53,568 KB
testcase_91	AC	58 ms 53,580 KB
testcase_92	AC	59 ms 53,492 KB
testcase_93	AC	58 ms 53,496 KB
testcase_94	AC	59 ms 53,024 KB
testcase_95	AC	58 ms 53,576 KB
testcase_96	AC	57 ms 53,564 KB
testcase_97	AC	59 ms 53,576 KB
testcase_98	AC	59 ms 52,372 KB
testcase_99	AC	56 ms 53,484 KB
testcase_100	AC	57 ms 53,572 KB
testcase_101	AC	60 ms 53,576 KB
testcase_102	AC	60 ms 52,440 KB
testcase_103	AC	58 ms 52,468 KB
testcase_104	AC	57 ms 53,484 KB
testcase_105	AC	55 ms 52,520 KB
testcase_106	AC	57 ms 53,568 KB
testcase_107	AC	58 ms 53,580 KB
testcase_108	AC	60 ms 53,568 KB
testcase_109	AC	60 ms 52,632 KB
testcase_110	AC	59 ms 52,384 KB
testcase_111	AC	58 ms 52,356 KB
testcase_112	AC	60 ms 53,564 KB
testcase_113	AC	60 ms 53,572 KB
testcase_114	AC	59 ms 53,572 KB
testcase_115	AC	58 ms 53,568 KB
testcase_116	AC	57 ms 52,460 KB
testcase_117	AC	58 ms 53,568 KB
testcase_118	AC	57 ms 53,488 KB
testcase_119	AC	56 ms 53,492 KB
testcase_120	AC	57 ms 53,572 KB
testcase_121	AC	57 ms 53,496 KB
testcase_122	AC	57 ms 53,496 KB
testcase_123	AC	58 ms 53,572 KB
testcase_124	AC	57 ms 52,500 KB
testcase_125	AC	56 ms 53,488 KB
testcase_126	AC	57 ms 52,360 KB
testcase_127	AC	57 ms 53,568 KB
testcase_128	AC	311 ms 68,984 KB
testcase_129	AC	605 ms 88,852 KB
testcase_130	AC	490 ms 75,752 KB
testcase_131	AC	744 ms 91,992 KB
testcase_132	AC	969 ms 92,116 KB
testcase_133	AC	81 ms 54,524 KB
testcase_134	AC	135 ms 55,760 KB
testcase_135	AC	330 ms 69,816 KB
testcase_136	AC	373 ms 69,260 KB
testcase_137	AC	226 ms 69,256 KB
testcase_138	AC	672 ms 81,848 KB
testcase_139	AC	622 ms 88,348 KB
testcase_140	AC	267 ms 63,736 KB
testcase_141	AC	818 ms 92,928 KB
testcase_142	AC	392 ms 71,828 KB
testcase_143	AC	241 ms 70,796 KB
testcase_144	AC	620 ms 89,212 KB
testcase_145	AC	134 ms 57,980 KB
testcase_146	AC	251 ms 65,644 KB
testcase_147	AC	516 ms 80,884 KB
testcase_148	AC	380 ms 72,064 KB
testcase_149	AC	599 ms 85,056 KB
testcase_150	AC	659 ms 90,680 KB
testcase_151	AC	125 ms 56,348 KB
testcase_152	AC	231 ms 67,448 KB
testcase_153	AC	316 ms 74,136 KB
testcase_154	AC	108 ms 55,764 KB
testcase_155	AC	647 ms 88,860 KB
testcase_156	AC	301 ms 68,316 KB
testcase_157	AC	659 ms 88,836 KB
testcase_158	AC	803 ms 91,612 KB
testcase_159	AC	222 ms 63,784 KB
testcase_160	AC	122 ms 55,820 KB
testcase_161	AC	885 ms 89,908 KB
testcase_162	AC	254 ms 62,476 KB
testcase_163	AC	231 ms 69,324 KB
testcase_164	AC	1,007 ms 92,216 KB
testcase_165	AC	655 ms 88,720 KB
testcase_166	AC	221 ms 61,756 KB
testcase_167	AC	480 ms 73,972 KB
testcase_168	AC	364 ms 68,692 KB
testcase_169	AC	402 ms 71,980 KB
testcase_170	AC	341 ms 68,584 KB
testcase_171	AC	484 ms 75,376 KB
testcase_172	AC	388 ms 72,156 KB
testcase_173	AC	155 ms 56,332 KB
testcase_174	AC	685 ms 90,096 KB
testcase_175	AC	1,005 ms 95,168 KB
testcase_176	AC	634 ms 87,072 KB
testcase_177	AC	165 ms 60,320 KB
testcase_178	AC	637 ms 86,844 KB
testcase_179	AC	726 ms 90,416 KB
testcase_180	AC	260 ms 62,568 KB
testcase_181	AC	124 ms 56,028 KB
testcase_182	AC	161 ms 58,848 KB
testcase_183	AC	190 ms 59,552 KB
testcase_184	AC	164 ms 58,816 KB
testcase_185	AC	218 ms 62,756 KB
testcase_186	AC	242 ms 62,968 KB
testcase_187	AC	197 ms 61,448 KB
testcase_188	AC	55 ms 53,492 KB
testcase_189	AC	56 ms 52,404 KB
testcase_190	AC	56 ms 53,564 KB
testcase_191	AC	58 ms 52,600 KB
testcase_192	AC	58 ms 53,572 KB
testcase_193	AC	57 ms 53,496 KB
testcase_194	AC	56 ms 53,484 KB
testcase_195	AC	59 ms 52,552 KB
testcase_196	AC	519 ms 81,024 KB
testcase_197	AC	242 ms 64,116 KB
testcase_198	AC	443 ms 73,040 KB
testcase_199	AC	572 ms 86,840 KB
testcase_200	AC	239 ms 62,936 KB
testcase_201	AC	159 ms 59,264 KB
testcase_202	AC	592 ms 89,160 KB
testcase_203	AC	382 ms 72,092 KB
testcase_204	AC	767 ms 92,832 KB
testcase_205	AC	385 ms 72,520 KB
testcase_206	AC	356 ms 88,264 KB
testcase_207	AC	219 ms 62,676 KB
testcase_208	AC	633 ms 87,940 KB
testcase_209	AC	272 ms 68,348 KB
testcase_210	AC	174 ms 60,588 KB
testcase_211	AC	360 ms 71,184 KB
testcase_212	AC	172 ms 61,632 KB
testcase_213	AC	245 ms 71,660 KB
testcase_214	AC	780 ms 92,700 KB
testcase_215	AC	577 ms 90,416 KB
testcase_216	AC	863 ms 92,396 KB
testcase_217	AC	460 ms 75,624 KB
testcase_218	AC	260 ms 63,256 KB
testcase_219	AC	256 ms 71,620 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

結果

テストケース

ソースコード