結果

問題 No.1864 Shortest Paths Counting
ユーザー pockynypockyny
提出日時 2022-03-04 23:27:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 355 ms / 2,000 ms
コード長 2,328 bytes
コンパイル時間 1,071 ms
コンパイル使用メモリ 93,556 KB
実行使用メモリ 14,332 KB
最終ジャッジ日時 2023-09-26 02:39:26
合計ジャッジ時間 7,146 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 209 ms
13,968 KB
testcase_10 AC 242 ms
13,848 KB
testcase_11 AC 242 ms
14,184 KB
testcase_12 AC 331 ms
13,964 KB
testcase_13 AC 249 ms
14,208 KB
testcase_14 AC 273 ms
13,908 KB
testcase_15 AC 243 ms
13,860 KB
testcase_16 AC 244 ms
13,912 KB
testcase_17 AC 238 ms
14,324 KB
testcase_18 AC 260 ms
13,948 KB
testcase_19 AC 283 ms
14,116 KB
testcase_20 AC 355 ms
14,024 KB
testcase_21 AC 298 ms
13,992 KB
testcase_22 AC 236 ms
13,884 KB
testcase_23 AC 212 ms
13,996 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 253 ms
13,956 KB
testcase_26 AC 119 ms
14,332 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
typedef long long ll;
ll INF = 1000000000000000;
ll mod = 998244353;
struct segment_tree{
    int n; vector<ll> seg;
    segment_tree(){}
    segment_tree(int sz){n = sz; seg.resize(2*n);}
    segment_tree(vector<ll> v){
        n = v.size(); seg.resize(2*n);
        for(int i=0;i<n;i++) seg[i + n] = v[i];
        for(int i=n - 1;i>0;i--) seg[i] = (seg[i<<1] + seg[i<<1|1])%mod;
    }
    void init(int sz){n = sz; seg.resize(2*n);}
    void update(int p,ll val){
        for((seg[p += n] += val) %= mod;p>1;p>>=1) seg[p>>1] = (seg[p] + seg[p^1])%mod;
    }
    ll query(int l,int r){
        ll res = 0;
        for(l += n,r += n; l<r;l>>=1,r>>=1){
            if(l&1) res = (res + seg[l++])%mod;
            if(r&1) res = (res + seg[--r])%mod;
        }
        return res;
    }
    void clear(){for(int i=0;i<2*n;i++) seg[i] = 0;}
};

ll x[200010],y[200010];
int main(){
    int i,n; cin >> n;
    vector<pair<ll,ll>> v;
    for(i=0;i<n;i++){
        cin >> x[i] >> y[i];
        v.push_back({x[i] + y[i],x[i] - y[i]});
    }
    ll sx = x[0] + y[0],sy = x[0] - y[0];
    ll gx = x[n - 1] + y[n - 1],gy = x[n - 1] - y[n - 1];
    for(i=0;i<n;i++){
        if(sx>gx) v[i].first *= -1;
        if(sy>gy) v[i].second *= -1;
    }
    if(sx>gx) sx *= -1, gx *= -1;
    if(sy>gy) sy *= -1, gy *= -1;
    sort(v.begin(),v.end());
    /*for(auto p:v){
        cout << p.first << " " << p.second << endl;
    }*/
    //cout << sx << " " << sy << " " << gx << " " << gy << endl;
    vector<ll> z(n);
    for(i=0;i<n;i++) z[i] = v[i].second;
    sort(z.begin(),z.end());
    segment_tree seg(n);
    bool f = false;
    ll ans = 0;
    for(i=0;i<n;i++){
        if(v[i].first==sx && v[i].second==sy) f = true;
        if(!f) continue;
        int j = lower_bound(z.begin(),z.end(),v[i].second) - z.begin();
        ll num = seg.query(0,j + 1);
        if(v[i].first==sx && v[i].second==sy) num++;
        if(v[i].first==gx && v[i].second==gy){
            ans = num;
            f = false;
        }
        seg.update(j,num);
    }
    int j = lower_bound(z.begin(),z.end(),gy) - z.begin();
    /*cout << seg.query(j,j + 1) << endl;
    for(i=0;i<n;i++) cout << seg.query(i,i + 1) << " ";
    cout << endl;*/
    cout << ans << endl;
}
0