結果
問題 | No.1170 Never Want to Walk |
ユーザー |
|
提出日時 | 2020-08-14 22:01:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 276 ms / 2,000 ms |
コード長 | 1,422 bytes |
コンパイル時間 | 1,457 ms |
コンパイル使用メモリ | 112,028 KB |
実行使用メモリ | 40,832 KB |
最終ジャッジ日時 | 2024-10-10 15:16:31 |
合計ジャッジ時間 | 6,311 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 37 |
ソースコード
#include<iostream> #include<string> #include<iomanip> #include<cmath> #include<vector> #include<algorithm> #include<utility> #include<set> #include<map> #include<queue> using namespace std; #define int long long #define endl "\n" constexpr long long INF = (long long)1e18; constexpr long long MOD = 1'000'000'007; struct fast_io { fast_io(){ std::cin.tie(nullptr); std::ios::sync_with_stdio(false); }; } fio; signed main(){ cout<<fixed<<setprecision(10); int count = 1; int N, A, B; vector<int> x; vector<int> used; set<int> s; map<int,int> mp; map<int,int> num; map<int,int> table; cin>>N>>A>>B; x.resize(N); used.resize(N); for(int i = 0; i < N; i++){ cin>>x[i]; s.insert(x[i]); table[x[i]] = i; } for(int i = 0; i < N; i++){ if(s.count(x[i]) == 0) continue; queue<int> Q; int sum = 0; Q.push(i); s.erase(x[i]); while(!Q.empty()){ int z = Q.front(); Q.pop(); int v = x[z]; sum++; num[z] = count; for(auto it = s.lower_bound(v - B); it != s.end();){ if(v - A < *it) break; Q.push(table[*it]); it = s.erase(it); } for(auto it = s.lower_bound(v + A); it != s.end();){ if(v + B < *it) break; Q.push(table[*it]); it = s.erase(it); } } mp[count] = sum; count++; } for(int i = 0; i < N; i++){ cout<<mp[num[i]]<<endl; } return 0; }