結果

問題 No.1864 Shortest Paths Counting
ユーザー tails
提出日時 2023-03-15 16:11:58
言語 cLay
(20241019-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
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

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