結果

問題 No.1170 Never Want to Walk
ユーザー kappybarkappybar
提出日時 2020-08-15 13:22:12
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,161 ms / 2,000 ms
コード長 2,910 bytes
コンパイル時間 2,465 ms
コンパイル使用メモリ 188,052 KB
実行使用メモリ 270,552 KB
最終ジャッジ日時 2024-10-10 17:45:53
合計ジャッジ時間 15,774 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 3 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 3 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 3 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 5 ms
5,248 KB
testcase_13 AC 5 ms
5,248 KB
testcase_14 AC 5 ms
5,248 KB
testcase_15 AC 5 ms
5,248 KB
testcase_16 AC 5 ms
5,248 KB
testcase_17 AC 6 ms
5,248 KB
testcase_18 AC 5 ms
5,248 KB
testcase_19 AC 5 ms
5,248 KB
testcase_20 AC 6 ms
5,248 KB
testcase_21 AC 5 ms
5,248 KB
testcase_22 AC 6 ms
5,248 KB
testcase_23 AC 6 ms
5,248 KB
testcase_24 AC 6 ms
5,248 KB
testcase_25 AC 6 ms
5,248 KB
testcase_26 AC 6 ms
5,248 KB
testcase_27 AC 738 ms
120,508 KB
testcase_28 AC 732 ms
120,752 KB
testcase_29 AC 714 ms
115,404 KB
testcase_30 AC 740 ms
120,392 KB
testcase_31 AC 721 ms
119,092 KB
testcase_32 AC 1,111 ms
250,304 KB
testcase_33 AC 1,161 ms
244,788 KB
testcase_34 AC 1,107 ms
236,616 KB
testcase_35 AC 1,133 ms
270,552 KB
testcase_36 AC 1,052 ms
249,524 KB
testcase_37 AC 1,052 ms
249,272 KB
testcase_38 AC 1,064 ms
235,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
using ll = long long ;
using P = pair<int,int> ;
using pll = pair<long long,long long>;
constexpr int INF = 1e9;
constexpr long long LINF = 1e17;
constexpr int MOD = 1000000007;
constexpr double PI = 3.14159265358979323846;


struct range_path{
    int n; 
    int N;
    int V;
    vector<vector<pair<long long,int>>> Graph;
    range_path(int n):n(n){
        N=1;
        while(N<n) N*=2;
        Graph.resize(3*N-2);
        V=3*N-2;
        for(int i=0;i<N-1;++i){
            Graph[i].emplace_back(0,2*i+1);
            Graph[i].emplace_back(0,2*i+2);
            Graph[2*i+N-1].emplace_back(0,i+2*N-1);
            Graph[2*i+N].emplace_back(0,i+2*N-1);
        }
    }
    void add_edge_from(int k,int l,int r,int p,int q,int v){
        if(r <= p || q <= l) return;
        if(l <= p && q <= r) Graph[3*N-3-k].emplace_back(0LL,v);
        else{
            add_edge_from(2*k+2,l,r,p,(p+q)/2,v);
            add_edge_from(2*k+1,l,r,(p+q)/2,q,v);
        }
    }
    void add_edge_to(int k,int L,int R,int p,int q,int v){
        if(R <= p || q <= L) return;
        if(L <= p && q <= R) Graph[v].emplace_back(0LL,k);
        else{
            add_edge_to(2*k+1,L,R,p,(p+q)/2,v);
            add_edge_to(2*k+2,L,R,(p+q)/2,q,v);
        }
    }
    void add_edge(int l,int r,int L,int R,long long cost){
        if(l>=r||L>=R) return;
        Graph.emplace_back();
        Graph.emplace_back();
        V+=2;
        add_edge_from(0,l,r,0,N,V-2);
        add_edge_to(0,L,R,0,N,V-1);
        Graph[V-2].emplace_back(cost,V-1);
    }
};
/*
int main(){
    int n;
    cin >> n;
    range_path G(n);
    G.add_edge(1,4,3,7,1);
    rep(i,G.V){
        for(auto j:G.Graph[i]) cout << j.first <<" " << j.second << "  ";
        cout << endl;
    }
    return 0;
}
*/


int main(){
    int n,a,b;
    cin >> n >> a >> b;
    vector<int> x(n);
    rep(i,n) cin >> x[i];
    range_path G(n);
    rep(i,n){
        int l = lower_bound(x.begin(),x.end(),x[i]+a) - x.begin();
        int r = upper_bound(x.begin(),x.end(),x[i]+b) - x.begin();
        G.add_edge(i,i+1,l,r,0);
        G.add_edge(l,r,i,i+1,0);
    }
    vector<int> ans(10*G.N+3,-1);
    rep(i,n){
        if(ans[i+G.N-1]>=0) continue;
        int id = i+G.N-1;
        queue<int> q;
        vector<int> vv;
        q.push(id);
        vv.push_back(id);
        int res = 0;
        while(!q.empty()){
            int next = q.front();
            q.pop();
            if(ans[next]>=0) continue;
            ans[next]=0;
            vv.push_back(next);
            if(G.N-1<=next&&next<G.N-1+n) ++res;
            for(auto j:G.Graph[next]){
                if(ans[j.second]>=0) continue;
                q.push(j.second);
            }
        }
        for(int j:vv) ans[j] = res; 
    }
    rep(i,n){
        cout << ans[i+G.N-1] << endl;
    }
    return 0;
}
0