結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
![]() |
提出日時 | 2020-08-15 20:04:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 309 ms / 2,000 ms |
コード長 | 1,451 bytes |
コンパイル時間 | 1,607 ms |
コンパイル使用メモリ | 171,796 KB |
実行使用メモリ | 7,936 KB |
最終ジャッジ日時 | 2024-10-10 21:48:54 |
合計ジャッジ時間 | 7,461 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
コンパイルメッセージ
main.cpp:15: warning: "DEBUG" redefined 15 | #define DEBUG(x) std::cerr << #x << " : " << (x) << std::endl; | main.cpp:14: note: this is the location of the previous definition 14 | #define DEBUG(x) ; |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; using P = pair<ll, ll>; const ll MOD = 1e9+7; // const ll MOD = 998244353; const ll INF = 1ll<<60; #define FOR(i,a,b) for (ll i=(a);i<(ll)(b);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() #define DEBUG(x) ; #define DEBUG(x) std::cerr << #x << " : " << (x) << std::endl; int dx[4]{0, 1, 0, -1}; int dy[4]{1, 0, -1, 0}; ll N, A, B; struct UnionFind { vector<long long> par; UnionFind(ll n) : par(n, -1) {} long long root(long long x) { if (par[x] < 0) return x; else return par[x] = root(par[x]); } bool merge(long long x, long long y) { x = root(x); y = root(y); if(x == y) return false; if (par[x] > par[y]) swap(x, y); par[x] += par[y]; par[y] = x; return true; } bool issame(long long x, long long y) { return root(x) == root(y); } long long size(long long x) { return -par[root(x)]; } }; int main(int argc, char **argv) { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> N >> A >> B; vector<ll> x(N); UnionFind uf(N); vector<ll> y(N); REP(i, N) cin >> x[i]; REP(i, N-1) { auto it = x.begin(); ll l = lower_bound(ALL(x), x[i]+A) - it; ll r = upper_bound(ALL(x), x[i]+B) - it - 1; if (r < l) continue; uf.merge(i, l); y[l]++; y[r]--; } REP(i, N-1) y[i+1] += y[i]; REP(i, N-1) { if (y[i] > 0) uf.merge(i, i+1); } REP(i, N) std::cout << uf.size(i) << std::endl; return 0; }