結果
問題 | No.1170 Never Want to Walk |
ユーザー | noritake |
提出日時 | 2020-08-15 10:25:03 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 378 ms / 2,000 ms |
コード長 | 3,193 bytes |
コンパイル時間 | 1,607 ms |
コンパイル使用メモリ | 173,940 KB |
実行使用メモリ | 7,296 KB |
最終ジャッジ日時 | 2024-10-10 17:22:15 |
合計ジャッジ時間 | 7,888 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 3 ms
5,248 KB |
testcase_13 | AC | 3 ms
5,248 KB |
testcase_14 | AC | 4 ms
5,248 KB |
testcase_15 | AC | 3 ms
5,248 KB |
testcase_16 | AC | 4 ms
5,248 KB |
testcase_17 | AC | 4 ms
5,248 KB |
testcase_18 | AC | 4 ms
5,248 KB |
testcase_19 | AC | 3 ms
5,248 KB |
testcase_20 | AC | 3 ms
5,248 KB |
testcase_21 | AC | 4 ms
5,248 KB |
testcase_22 | AC | 4 ms
5,248 KB |
testcase_23 | AC | 4 ms
5,248 KB |
testcase_24 | AC | 4 ms
5,248 KB |
testcase_25 | AC | 4 ms
5,248 KB |
testcase_26 | AC | 4 ms
5,248 KB |
testcase_27 | AC | 355 ms
7,168 KB |
testcase_28 | AC | 346 ms
6,912 KB |
testcase_29 | AC | 359 ms
7,296 KB |
testcase_30 | AC | 360 ms
7,168 KB |
testcase_31 | AC | 351 ms
6,912 KB |
testcase_32 | AC | 357 ms
7,168 KB |
testcase_33 | AC | 359 ms
7,040 KB |
testcase_34 | AC | 360 ms
7,040 KB |
testcase_35 | AC | 360 ms
7,040 KB |
testcase_36 | AC | 354 ms
7,040 KB |
testcase_37 | AC | 354 ms
7,040 KB |
testcase_38 | AC | 378 ms
7,168 KB |
ソースコード
#include <bits/stdc++.h> #define rep(i, n) for (int i = 0; i < (int)(n); i++) using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<long long> vl; typedef vector<bool> vb; typedef vector<char> vc; #define INF __INT32_MAX__ #define LINF __LONG_LONG_MAX__ /** * UnionFind(重みなし) */ class UnionFind { private: vector<long long> parents; public: UnionFind(long long N) { this->parents = vector<long long>(N, -1); } long long size(long long A) { return -1 * parents[this->root(A)]; } long long root(long long A) { if (this->parents[A] < 0) return A; this->parents[A] = this->root(this->parents[A]); return this->parents[A]; } bool unite(long long A, long long B) { long long ra = this->root(A); long long rb = this->root(B); if (ra == rb) return false; if (this->size(ra) > this->size(rb)) { this->parents[ra] += this->parents[rb]; this->parents[rb] = ra; } else { this->parents[rb] += this->parents[ra]; this->parents[ra] = rb; } return true; } bool isUnite(long long A, long long B) { return this->root(A) == this->root(B); } void show() { for (int i = 0; i < this->parents.size(); i++) { this->root(i); // 親の更新を行う cout << "i: " << i << ", parents[i]: " << this->parents[i] << endl; } } }; int main() { ll N, A, B; cin >> N >> A >> B; vl X(N + 2); rep(i, N) cin >> X[i + 1]; X[0] = 0; X[N + 1] = LINF; UnionFind uni(N); vi imos(N); for (int i = 0; i < N; i++) { int l = i; int r = N + 2; while (r - l >= 1) { int mid = (l + r) / 2; ll d = X[mid] - X[i + 1]; if (d >= A) { r = mid; } else { l = mid + 1; } } int ra = r; l = i; r = N + 2; while (r - l >= 1) { int mid = (l + r) / 2; ll d = X[mid] - X[i + 1]; if (d > B) { r = mid; } else { l = mid + 1; } } int rb = r; /* ここで最悪N^2の辺を貼ってしまうからTLE for (ll j = ra; j < rb; j++) { if (!uni.isUnite(i, j - 1)) uni.unite(i, j - 1); } */ if (ra < rb) { uni.unite(i, ra - 1); imos[ra - 1]++; imos[rb - 2]--; } // cout << "i: " << (i + 1) << ", X[i]: " << X[i + 1] << ", ra: " << ra << ", X[ra]: " << X[ra] << ", rb: " << rb << ", X[rb]: " << X[rb] << endl; // cout << endl; } rep(i, N - 1) imos[i + 1] += imos[i]; // rep(i, N) cout << "i: " << i << ", imos[i]: " << imos[i] << endl; rep(i, N - 1) { if (imos[i] > 0) uni.unite(i, i + 1); } for (ll i = 0; i < N; i++) { cout << uni.size(i) << endl; } }