結果
| 問題 |
No.1170 Never Want to Walk
|
| コンテスト | |
| ユーザー |
 NyaanNyaan
|
| 提出日時 | 2020-08-15 19:51:55 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 126 ms / 2,000 ms |
| コード長 | 8,578 bytes |
| コンパイル時間 | 4,133 ms |
| コンパイル使用メモリ | 306,704 KB |
| 最終ジャッジ日時 | 2025-01-13 01:43:38 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 37 |
ソースコード
#pragma region kyopro_template
#define Nyaan_template
#include <immintrin.h>
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define each(x, v) for (auto &x : v)
#define all(v) (v).begin(), (v).end()
#define sz(v) ((int)(v).size())
#define mem(a, val) memset(a, val, sizeof(a))
#define ini(...) \
int __VA_ARGS__; \
in(__VA_ARGS__)
#define inl(...) \
long long __VA_ARGS__; \
in(__VA_ARGS__)
#define ins(...) \
string __VA_ARGS__; \
in(__VA_ARGS__)
#define inc(...) \
char __VA_ARGS__; \
in(__VA_ARGS__)
#define in2(s, t) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i]); \
}
#define in3(s, t, u) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i]); \
}
#define in4(s, t, u, v) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i], v[i]); \
}
#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)
#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)
#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)
#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)
#define reg(i, a, b) for (long long i = (a); i < (b); i++)
#define die(...) \
do { \
out(__VA_ARGS__); \
return; \
} while (0)
using namespace std;
using ll = long long;
template <class T>
using V = vector<T>;
using vi = vector<int>;
using vl = vector<long long>;
using vvi = vector<vector<int>>;
using vd = V<double>;
using vs = V<string>;
using vvl = vector<vector<long long>>;
using P = pair<long long, long long>;
using vp = vector<P>;
using pii = pair<int, int>;
using vpi = vector<pair<int, int>>;
constexpr int inf = 1001001001;
constexpr long long infLL = (1LL << 61) - 1;
template <typename T, typename U>
inline bool amin(T &x, U y) {
return (y < x) ? (x = y, true) : false;
}
template <typename T, typename U>
inline bool amax(T &x, U y) {
return (x < y) ? (x = y, true) : false;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << p.first << " " << p.second;
return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
int s = (int)v.size();
for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (auto &x : v) is >> x;
return is;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &... u) {
cin >> t;
in(u...);
}
void out() { cout << "\n"; }
template <typename T, class... U>
void out(const T &t, const U &... u) {
cout << t;
if (sizeof...(u)) cout << " ";
out(u...);
}
#ifdef NyaanDebug
#define trc(...) \
do { \
cerr << #__VA_ARGS__ << " = "; \
dbg_out(__VA_ARGS__); \
} while (0)
#define trca(v, N) \
do { \
cerr << #v << " = "; \
array_out(v, N); \
} while (0)
#define trcc(v) \
do { \
cerr << #v << " = {"; \
each(x, v) { cerr << " " << x << ","; } \
cerr << "}" << endl; \
} while (0)
template <typename T>
void _cout(const T &c) {
cerr << c;
}
void _cout(const int &c) {
if (c == 1001001001)
cerr << "inf";
else if (c == -1001001001)
cerr << "-inf";
else
cerr << c;
}
void _cout(const unsigned int &c) {
if (c == 1001001001)
cerr << "inf";
else
cerr << c;
}
void _cout(const long long &c) {
if (c == 1001001001 || c == (1LL << 61) - 1)
cerr << "inf";
else if (c == -1001001001 || c == -((1LL << 61) - 1))
cerr << "-inf";
else
cerr << c;
}
void _cout(const unsigned long long &c) {
if (c == 1001001001 || c == (1LL << 61) - 1)
cerr << "inf";
else
cerr << c;
}
template <typename T, typename U>
void _cout(const pair<T, U> &p) {
cerr << "{ ";
_cout(p.fi);
cerr << ", ";
_cout(p.se);
cerr << " } ";
}
template <typename T>
void _cout(const vector<T> &v) {
int s = v.size();
cerr << "{ ";
for (int i = 0; i < s; i++) {
cerr << (i ? ", " : "");
_cout(v[i]);
}
cerr << " } ";
}
template <typename T>
void _cout(const vector<vector<T>> &v) {
cerr << "[ ";
for (const auto &x : v) {
cerr << endl;
_cout(x);
cerr << ", ";
}
cerr << endl << " ] ";
}
void dbg_out() { cerr << endl; }
template <typename T, class... U>
void dbg_out(const T &t, const U &... u) {
_cout(t);
if (sizeof...(u)) cerr << ", ";
dbg_out(u...);
}
template <typename T>
void array_out(const T &v, int s) {
cerr << "{ ";
for (int i = 0; i < s; i++) {
cerr << (i ? ", " : "");
_cout(v[i]);
}
cerr << " } " << endl;
}
template <typename T>
void array_out(const T &v, int H, int W) {
cerr << "[ ";
for (int i = 0; i < H; i++) {
cerr << (i ? ", " : "");
array_out(v[i], W);
}
cerr << " ] " << endl;
}
#else
#define trc(...)
#define trca(...)
#define trcc(...)
#endif
inline int popcnt(unsigned long long a) { return __builtin_popcountll(a); }
inline int lsb(unsigned long long a) { return __builtin_ctzll(a); }
inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); }
template <typename T>
inline int getbit(T a, int i) {
return (a >> i) & 1;
}
template <typename T>
inline void setbit(T &a, int i) {
a |= (1LL << i);
}
template <typename T>
inline void delbit(T &a, int i) {
a &= ~(1LL << i);
}
template <typename T>
int lb(const vector<T> &v, const T &a) {
return lower_bound(begin(v), end(v), a) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, const T &a) {
return upper_bound(begin(v), end(v), a) - begin(v);
}
template <typename T>
int btw(T a, T x, T b) {
return a <= x && x < b;
}
template <typename T, typename U>
T ceil(T a, U b) {
return (a + b - 1) / b;
}
constexpr long long TEN(int n) {
long long ret = 1, x = 10;
while (n) {
if (n & 1) ret *= x;
x *= x;
n >>= 1;
}
return ret;
}
template <typename T>
vector<T> mkrui(const vector<T> &v) {
vector<T> ret(v.size() + 1);
for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];
return ret;
};
template <typename T>
vector<T> mkuni(const vector<T> &v) {
vector<T> ret(v);
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret;
}
template <typename F>
vector<int> mkord(int N, F f) {
vector<int> ord(N);
iota(begin(ord), end(ord), 0);
sort(begin(ord), end(ord), f);
return ord;
}
template <typename T = int>
vector<T> mkiota(int N) {
vector<T> ret(N);
iota(begin(ret), end(ret), 0);
return ret;
}
template <typename T>
vector<int> mkinv(vector<T> &v) {
vector<int> inv(v.size());
for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i;
return inv;
}
struct IoSetupNya {
IoSetupNya() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(7);
}
} iosetupnya;
void solve();
int main() { solve(); }
#pragma endregion
// Range Union Find
struct RangeUnionFind {
vector<int> data, left, right;
RangeUnionFind(int N) : data(N, -1) {
left.resize(N);
right.resize(N);
iota(begin(left), end(left), 0);
iota(begin(right), end(right), 1);
}
int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); }
int unite(int x, int y) {
if ((x = find(x)) == (y = find(y))) return false;
if (data[x] > data[y]) swap(x, y);
data[x] += data[y];
data[y] = x;
left[x] = min(left[x], left[y]);
right[x] = max(right[x], right[y]);
return true;
}
// unite [l, r)
void range_unite(int l, int r) {
if ((l = max(l, 0)) >= (r = min(r, (int)data.size()))) return;
int m;
while ((m = right[find(l)]) < r) {
assert(left[find(m)] == m);
unite(l, m);
}
}
int size(int k) { return -data[find(k)]; }
int same(int x, int y) { return find(x) == find(y); }
};
void solve() {
inl(N, A, B);
vl x(N);
in(x);
RangeUnionFind uf(N);
rep(i, N) {
int l = lb(x, x[i] + A);
int r = lb(x, x[i] + B + 1);
trc(i,l,r);
uf.range_unite(l, r);
}
rep(i, N) {
int l = lb(x, x[i] + A);
int r = lb(x, x[i] + B + 1);
if(l != r) uf.unite(l, i);
}
rep(i, N) out(uf.size(i));
}