結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
|
提出日時 | 2021-09-22 17:46:52 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 436 ms / 2,000 ms |
コード長 | 1,783 bytes |
コンパイル時間 | 1,229 ms |
コンパイル使用メモリ | 90,000 KB |
実行使用メモリ | 6,400 KB |
最終ジャッジ日時 | 2024-07-05 08:50:03 |
合計ジャッジ時間 | 8,414 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <string.h> #include <iostream> #include <sstream> #include <algorithm> #include <stack> #include <vector> #include <queue> #include <map> #include <set> #include <deque> #include <functional> #define _USE_MATH_DEFINES #include <math.h> #include <complex> using namespace std; //#include <atcoder/all> //using namespace atcoder; #define REP(i,n) for(int i = 0; i < (int)n; i++) #define RREP(i,n) for(int i = (int)n-1; i >= 0; i--) #define LREP(i,n) for(LL i = 0; i < (LL)n; i++) #define Vi vector<int> #define Vl vector<long long> #define LP pair<long long ,long long> #define P pair<int, int> #define T3 tuple<LL, LL, LL> #define T4 tuple<LL, LL, LL, LL> #define INF 1000000007 #define SIZE 300010 #define MOD 1000000007 typedef long long LL; int N, A, B; int X[SIZE]; int parent[SIZE], s[SIZE]; void init() { REP(i, N) { parent[i] = i; s[i] = 1; } } int par(int a) { if (parent[a] == a) return a; else return parent[a] = par(parent[a]); } void merge(int a, int b) { int pa = par(a), pb = par(b); if(pa != pb) { parent[pb] = pa; s[pa] += s[pb]; } } bool same(int a, int b) { int pa = par(a), pb = par(b); if (pa == pb) return true; else return false; } int size(int a) { int pa = par(a); return s[pa]; } int main() { cin >> N >> A >> B; REP(i, N) cin >> X[i]; X[N] = 2 * INF; init(); queue<int> que; int left = 0, right = 0; REP(i, N) { while (X[right] <= B + X[i]) { que.push(X[right]); right += 1; } while (X[left] < A + X[i] && que.size()) { que.pop(); left += 1; } if (que.size()) { merge(i, left); } for (int j = right - 1; j > left; j--) { if (same(j, j - 1)) break; else merge(j, j - 1); } } REP(i, N) { cout << size(i) << endl; } }