結果

問題 No.1864 Shortest Paths Counting
ユーザー tailstails
提出日時 2023-03-15 16:11:58
言語 cLay
(20240714-1)
結果
AC  
実行時間 35 ms / 2,000 ms
コード長 457 bytes
コンパイル時間 8,222 ms
コンパイル使用メモリ 229,560 KB
実行使用メモリ 12,416 KB
最終ジャッジ日時 2024-09-18 08:48:17
合計ジャッジ時間 11,441 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 1 ms
5,248 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 1 ms
5,376 KB
testcase_09 AC 35 ms
12,416 KB
testcase_10 AC 27 ms
10,880 KB
testcase_11 AC 27 ms
11,008 KB
testcase_12 AC 29 ms
11,264 KB
testcase_13 AC 27 ms
11,008 KB
testcase_14 AC 26 ms
11,008 KB
testcase_15 AC 27 ms
11,136 KB
testcase_16 AC 26 ms
10,752 KB
testcase_17 AC 27 ms
11,136 KB
testcase_18 AC 26 ms
11,008 KB
testcase_19 AC 31 ms
11,136 KB
testcase_20 AC 26 ms
11,008 KB
testcase_21 AC 24 ms
10,752 KB
testcase_22 AC 25 ms
11,008 KB
testcase_23 AC 23 ms
10,880 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 23 ms
9,216 KB
testcase_26 AC 17 ms
10,752 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define MD 998244353
ll@n,x[n],y[];
rd((x,y)(n));
rrep(i,n)x[i]-=x[0],y[i]-=y[0];
if(abs(x[n-1])<abs(y[n-1])){
	rep(i,n)swap(x[i],y[i]);
}
if(x[n-1]<0){
	rep(i,n)x[i]=-x[i];
}
rep(i,n)(x[i],y[i])=(x[i]+y[i],x[i]-y[i]);
ll x9=x[n-1],y9=y[n-1];
sortA(n,x,y);
ll s=0;
while(x[s]|y[s])++s;
ll t=s+1;
while(x[t]-x9|y[t]-y9)++t;
++t;
coordcomp(t-s,y+s);
fenwick<Mint>f;
f.malloc(n,1);
f.add(y[s],1);
rep(i,s+1,t-1){
	f.add(y[i],f.get(y[i]));
}
wt(f.get(y[t-1]));
0