#849344 (cLay) No.1864 Shortest Paths Counting

• 問題: No.1864 Shortest Paths Counting
• ユーザー: tails
• 提出日時: 2023-03-15 16:11:58
• 言語: cLay (20240104-1)
• 結果: AC
• 実行時間: 37 ms / 2,000 ms
• コード長: 457 bytes
• コンパイル時間: 9,067 ms
• コンパイル使用メモリ: 230,180 KB
• 実行使用メモリ: 16,652 KB
• 最終ジャッジ日時: 2023-10-18 12:27:25
• 合計ジャッジ時間: 12,711 ms
• ジャッジサーバーID （参考情報）: judge13 / judge12

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	3 ms; 7,828 KB
testcase_01	AC	3 ms; 7,828 KB
testcase_02	AC	3 ms; 7,828 KB
testcase_03	AC	2 ms; 7,828 KB
testcase_04	AC	2 ms; 7,828 KB
testcase_05	AC	2 ms; 7,828 KB
testcase_06	AC	2 ms; 7,828 KB
testcase_07	AC	2 ms; 7,828 KB
testcase_08	AC	2 ms; 7,828 KB
testcase_09	AC	37 ms; 16,652 KB
testcase_10	AC	27 ms; 14,196 KB
testcase_11	AC	28 ms; 14,200 KB
testcase_12	AC	29 ms; 14,316 KB
testcase_13	AC	28 ms; 14,220 KB
testcase_14	AC	26 ms; 14,132 KB
testcase_15	AC	27 ms; 14,188 KB
testcase_16	AC	25 ms; 14,096 KB
testcase_17	AC	27 ms; 14,184 KB
testcase_18	AC	27 ms; 14,184 KB
testcase_19	AC	31 ms; 14,376 KB
testcase_20	AC	27 ms; 14,160 KB
testcase_21	AC	24 ms; 14,032 KB
testcase_22	AC	27 ms; 14,168 KB
testcase_23	AC	24 ms; 14,060 KB
testcase_24	AC	2 ms; 7,828 KB
testcase_25	AC	24 ms; 11,984 KB
testcase_26	AC	16 ms; 14,032 KB

ソースコード

#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]));