結果

問題 No.1170 Never Want to Walk
コンテスト
ユーザー 달콤한마시로
提出日時 2025-12-29 07:48:38
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 65 ms / 2,000 ms
コード長 1,689 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 413 ms
コンパイル使用メモリ 35,048 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-29 07:48:43
合計ジャッジ時間 4,275 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘ll readint()’:
main.cpp:39:34: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   39 | ll readint() { long long n; scanf("%lld", &n); return n; }
      |                             ~~~~~^~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <cassert>
#include <cstdio>
#include <utility>

using std::scanf;
using std::printf;

using ll = long long;

const int MAXN = 200000 + 10;

int arr[MAXN];
int df[MAXN];
int rt[MAXN];
int uffind(int i) {
    if (rt[i] < 0) {
        return i;
    }
    return (rt[i] = uffind(rt[i]));
}
void ufunion(int i, int j) {
    i = uffind(i);
    j = uffind(j);
    if (i == j) return;
    if (-rt[i] < -rt[j]) {
        using std::swap;
        swap(rt[i], rt[j]);
    }
    rt[i] += rt[j];
    rt[j] = i;
}
void add_edge(int i, int j) {
    ufunion(i, j);
}
int get_sz(int i) {
    return -rt[uffind(i)];
}

ll readint() { long long n; scanf("%lld", &n); return n; }

signed main() {
    int n = readint();
    int a = readint();
    int b = readint();
    for (int i = 0; i < n; ++i) {
        rt[i] = -1;
    }
    for (int i = 0; i < n; ++i) {
        arr[i] = readint();
    }
    int i_lft_a = 0;
    int i_lft_b = 0;
    for (int i = 0; i < n; ++i) {
        while (i_lft_b < i && arr[i] - arr[i_lft_b] > b) ++i_lft_b;
        while (i_lft_a < i && arr[i] - arr[i_lft_a] >= a) ++i_lft_a;
        if (i_lft_b < i_lft_a) {
            assert(a <= arr[i] - arr[i_lft_b] && arr[i] - arr[i_lft_b] <= b);
            assert(a <= arr[i] - arr[i_lft_a - 1] && arr[i] - arr[i_lft_a - 1] <= b);
            add_edge(i_lft_b, i);
            df[i_lft_b]++;
            df[i_lft_a - 1]--;
        }
    }
    int c = 0;
    for (int i = 0; i < n; ++i) {
        c += df[i];
        if (c > 0) {
            add_edge(i, i + 1);
        }
    }
    c += df[n];
    assert(c == 0);
    for (int i = 0; i < n; ++i) {
        int ans = get_sz(i);
        printf("%d\n", ans);
    }
    return 0;
}
0