結果

問題 No.1170 Never Want to Walk
ユーザー goto_isyukugoto_isyuku
提出日時 2020-08-15 13:16:18
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 161 ms / 2,000 ms
コード長 2,998 bytes
コンパイル時間 1,959 ms
コンパイル使用メモリ 169,100 KB
実行使用メモリ 6,632 KB
最終ジャッジ日時 2024-04-19 00:56:43
合計ジャッジ時間 6,088 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 1 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 3 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 3 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 156 ms
6,600 KB
testcase_28 AC 155 ms
6,332 KB
testcase_29 AC 161 ms
6,620 KB
testcase_30 AC 161 ms
6,364 KB
testcase_31 AC 157 ms
6,472 KB
testcase_32 AC 153 ms
6,352 KB
testcase_33 AC 160 ms
6,340 KB
testcase_34 AC 151 ms
6,624 KB
testcase_35 AC 157 ms
6,616 KB
testcase_36 AC 152 ms
6,340 KB
testcase_37 AC 150 ms
6,600 KB
testcase_38 AC 154 ms
6,632 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#define rep(X,N) for(ll X = 0LL; X < (N); X++)
#define ALL(V) (V).begin(),(V).end()
#define endl "\n"

using namespace std;
typedef long long ll;

const double PI = 3.1415926535897932384626;
const ll MODN = 1000000007;
const ll MODN2 = 998244353;
const double EPS = 1e-10;

class UnionFind{
public:

    vector<int> root;
    vector<int> rank;
    vector<int> sizev;

    UnionFind();

    //1-indexでアクセスすること想定
    UnionFind(int n){

        for(int i = 0; i <= n; i++){
            root.push_back(i);
            rank.push_back(1);
            sizev.push_back(1);
        }
    }

    int find(int n){

        vector<int> update;
        int count = 0;

        while(n != root[n]){
            
            update.push_back(n);
            n = root[n];
            count++;
        }

        for(int i = 0; i < count; i++){
            root[update[i]] = n;
        }

        return n;
    }

    int size(int n){
        return sizev[find(n)];
    }

    void merge(int a, int b){

        a = find(a);
        b = find(b);

        if(a != b){

            if(rank[a] < rank[b]){
                root[a] = b;
                sizev[b] += sizev[a];
            }else{
                root[b] = a;
                sizev[a] += sizev[b];

                if(rank[a] == rank[b]){
                    rank[a]++;
                }
            }
        
        }
    }
};

//ソート済み配列に対して、指定した数以下の個数を返す関数
template<typename T>
int less_or_eq_count(std::vector<T> &v, T x){
    
    int ok = -1;
    int ng = v.size();

    while(ng - ok > 1){
        int tmp = (ok + ng) / 2;

        if(v[tmp] <= x){
            ok = tmp;
        }else ng = tmp;
    }

    return ok + 1;
}

//ソート済み配列に対して、指定した数以上の個数を返す関数
template<typename T>
int greater_or_eq_count(std::vector<T> &v, T x){
    
    int size = v.size();
    int ok = size;
    int ng = -1;

    while(ok - ng > 1){
        int tmp = (ok + ng) / 2;

        if(x <= v[tmp]){
            ok = tmp;
        }else ng = tmp;
    }

    return size - ok;
}

int main(){

    int n, a, b;
    cin >> n >> a >> b;

    vector<int> v(n);

    rep(i, n) cin >> v[i];

    UnionFind uf(n);

    int old_left = 0;
    int old_right = 0;

    rep(i, n){

        int plusa_count = greater_or_eq_count(v, v[i] + a);
        int plusb_count = less_or_eq_count(v, v[i] + b);

        int left = n - plusa_count;
        int right = plusb_count - 1;

        if(left == n) break;

        if(old_right < left){
            for(int j = left; j <= right; j++){
                uf.merge(i, j);
            }
        }else{
            if(i != 0) uf.merge(i, i - 1);

            for(int j = old_right + 1; j <= right; j++){
                uf.merge(i, j);
            }
        }

        old_left = left;
        old_right = right;
    }

    rep(i, n){
        cout << uf.size(i) << endl;
    }

    return 0;
}
0