結果

問題 No.1170 Never Want to Walk
ユーザー goto_isyuku
提出日時 2020-08-15 13:16:18
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 160 ms / 2,000 ms
コード長 2,998 bytes
コンパイル時間 1,835 ms
コンパイル使用メモリ 172,940 KB
実行使用メモリ 6,756 KB
最終ジャッジ日時 2024-10-10 17:44:33
合計ジャッジ時間 5,926 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

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