結果
問題 | No.1864 Shortest Paths Counting |
ユーザー |
![]() |
提出日時 | 2022-03-04 22:37:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 405 ms / 2,000 ms |
コード長 | 1,334 bytes |
コンパイル時間 | 4,930 ms |
コンパイル使用メモリ | 261,188 KB |
最終ジャッジ日時 | 2025-01-28 05:39:59 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 23 |
ソースコード
#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 1000000000 int 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<long long> 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]); }); segtree<mint,op,e> seg(t.size()+7); 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; }