結果

問題 No.1170 Never Want to Walk
ユーザー goto_isyukugoto_isyuku
提出日時 2020-08-15 13:05:33
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,894 bytes
コンパイル時間 1,615 ms
コンパイル使用メモリ 173,956 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-10-10 17:42:24
合計ジャッジ時間 5,211 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,820 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,820 KB
testcase_04 AC 1 ms
6,820 KB
testcase_05 AC 2 ms
6,820 KB
testcase_06 AC 2 ms
6,816 KB
testcase_07 AC 2 ms
6,820 KB
testcase_08 AC 2 ms
6,820 KB
testcase_09 AC 2 ms
6,816 KB
testcase_10 AC 2 ms
6,816 KB
testcase_11 AC 2 ms
6,820 KB
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 153 ms
6,816 KB
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
権限があれば一括ダウンロードができます

ソースコード

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);
        }

        old_left = left;
        old_right = right;
    }

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

    return 0;
}
0