/* tenkei90-036 */ #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; const int inf=1<<30; const ll INF=1LL<<62; typedef pair P; typedef pair PP; const ll MOD=998244353; const int dy[]={0,1,0,-1}; const int dx[]={1,0,-1,0}; const int mod = 998244353; struct mint { long long x; // typedef long long long long; mint(long long x=0):x((x%mod+mod)%mod){} mint operator-() const { return mint(-x);} mint& operator+=(const mint a) { if ((x += a.x) >= mod) x -= mod; return *this; } mint& operator-=(const mint a) { if ((x += mod-a.x) >= mod) x -= mod; return *this; } mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;} mint operator+(const mint a) const { return mint(*this) += a;}//後ろのconstはメンバxを変更しないことを示す mint operator-(const mint a) const { return mint(*this) -= a;} mint operator*(const mint a) const { return mint(*this) *= a;} bool operator==(const mint a) const {return a.x==x;} mint pow(unsigned long long int t) const { assert(t>=0); if (!t) return 1; //aがtで割り切れない場合には t%=(mod-1)をして良い mint a = pow(t>>1); a *= a; if (t&1) a *= *this; return a; } // for prime mod mint inv() const { return pow(mod-2);} mint& operator/=(const mint a) { return *this *= a.inv();} mint operator/(const mint a) const { return mint(*this) /= a;} }; std::istream& operator>>(std::istream& is, mint& a) { return is >> a.x;} std::ostream& operator<<(std::ostream& os, const mint& a) { return os << a.x;} struct combination { std::vector fact, ifact; combination(int n):fact(n+1),ifact(n+1) { assert(n < mod); fact[0] = 1; for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i; ifact[n] = fact[n].inv(); for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i; } mint operator()(int n, int k) { if (k < 0 || k > n) return 0; return fact[n]*ifact[k]*ifact[n-k]; } }; //座標圧縮 template struct compress{ std::set st; std::map mp; int sz; compress(const std::vector& a):sz(0){ for(auto x:a){ st.insert(x); } for(auto x:st){ mp[x]=sz++; } } int val(const T& x){ //ベクトルaの要素xに対応した要素を取り出す return mp[x]; } int size(){ return sz; } }; mint op(mint x, mint y){ //(x,y)を比較する任意の演算子.今回はmaxとした return (x+y); } mint e(){ //initialize value return 0; } template class segment_tree{ public: std::vector dat; int n=1; segment_tree(int n_){ while(n < n_){ n*=2; } dat = std::vector(2*n-1,e());// 0,1,2,...,2*n-1,2*n-2 } ~segment_tree(){ std::vector().swap(dat); } void set(int k,Type a){ update(k,a); } void update(int k,Type a){ k+=n-1; dat[k] = a; while(k>0){ k = (k-1)/2; dat[k]=op(dat[2*k+1],dat[2*k+2]); } } //[a,b) Type query(int a,int b,int k,int l,int r){ if(r<=a || b<=l) return e(); if(a<=l && r<=b) return dat[k]; else{ Type vl = query(a,b,2*k+1,l,(l+r)/2); Type vr = query(a,b,2*k+2,(l+r)/2,r); return op(vl,vr); } } //[a,b)の範囲でのmax Type query(int a,int b){ return query(a,b,0,0,n); } Type operator[](int index){ return get(index); } Type get(int index){ index += n-1; return dat[index]; } void add(int index,Type val){ update(index,op(get(index),val)); } }; int main(){ int N; cin>>N; vector X(N),Y(N); vector

XY(N); for(int i=0;i>X[i]>>Y[i]; XY[i].first = (X[i]+Y[i]); XY[i].second = (X[i]-Y[i]); } if(XY[0].first>XY[N-1].first){ for(int i=0;iXY[N-1].second){ for(int i=0;i points; for(int i=0;i dp(sz); // dp[0]=1; // for(int i=0;i py; for(auto [_,y]:XY){ py.push_back(y); } compress cp(py); for(int i=0;i dp(sz+5); segment_tree seg(sz+5); dp[0]=1; seg.set(XY[0].second,dp[0]); for(int i=1;i ord(N); // iota(ord.begin(),ord.end(),0); // sort(ord.begin(),ord.end(), // [&](const int lhs,const int rhs){ // if(XY[lhs].first==XY[rhs].first) return XY[lhs].second Y座標が小さい方 // vector y(N); // for(int i=0;i cp(y); // for(int i=0;i> mp; // for(int i=0;i dp(N+1,0); // dp[ord[0]]=1; // segment_tree seg(N+10); // seg.set(XY[ord[0]].second,dp[ord[0]]);//0番目のy座標にdp[0]を入れる // for( auto [_,vec]:mp){ // //[0,XY[ord[i]].second)までの // mint sum=0; // for(auto idx:vec){ // sum += seg.query(0,XY[idx].second); // } // for(auto idx:vec){ // dp[idx] = sum; // seg.add(XY[idx].second,dp[idx]); // } // } // mint ans=dp[ord[N-1]]; // cout<