結果
問題 | No.1864 Shortest Paths Counting |
ユーザー |
![]() |
提出日時 | 2022-03-04 22:31:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,344 bytes |
コンパイル時間 | 5,215 ms |
コンパイル使用メモリ | 262,460 KB |
最終ジャッジ日時 | 2025-01-28 05:37:21 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 12 WA * 1 RE * 10 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for(int i=0;i<(n);i++)#define Inf 1000000000int n;vector<long long> x,y;mint op(mint a,mint b){return a+b;}mint e(){return 0;}int main(){cin>>n;x.resize(n),y.resize(n);rep(i,n){cin>>x[i]>>y[i];long long t = x[i]+y[i];y[i] = x[i]-y[i];x[i] = t;}for(int i=n-1;i>=0;i--){y[i] -= y[0];x[i] -= x[0];}rep(i,n){if(y.back()<0)y[i] *= -1;if(x.back()<0)x[i] *= -1;}vector<int> t;rep(i,n){t.push_back(x[i]);t.push_back(y[i]);}sort(t.begin(),t.end());t.erase(unique(t.begin(),t.end()),t.end());rep(i,n){x[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),x[i]));y[i] = distance(t.begin(),lower_bound(t.begin(),t.end(),y[i]));}vector<int> ind(n);rep(i,n)ind[i] = i;sort(ind.begin(),ind.end(),[&](int a,int b){return make_pair(x[a],y[a])<make_pair(x[b],y[b]);});bool f = false;segtree<mint,op,e> seg(t.size());mint ans;rep(i,n){if(ind[i]==0){seg.set(y[ind[i]],1);}else if(ind[i]==n-1){ans = seg.prod(0,y[ind[i]]+1);}else{mint tt = seg.prod(0,y[ind[i]]+1);seg.set(y[ind[i]],seg.get(y[ind[i]])+tt);}}cout<<ans.val()<<endl;return 0;}