結果
問題 |
No.1170 Never Want to Walk
|
ユーザー |
|
提出日時 | 2025-05-01 18:27:50 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,404 bytes |
コンパイル時間 | 4,379 ms |
コンパイル使用メモリ | 330,772 KB |
実行使用メモリ | 10,112 KB |
最終ジャッジ日時 | 2025-05-01 18:27:58 |
合計ジャッジ時間 | 7,947 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 WA * 1 |
other | AC * 7 WA * 30 |
ソースコード
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define ar array #define int long long #define ll long long #define ld long double #define pb push_back #define eb emplace_back #define pob pop_back() #define nn "\n" #define onn << "\n" #define ee endl #define oee << endl #define ss " " #define oss << " " #define sei unordered_set<int, custom_hash> #define ses unordered_set<string> #define ma unordered_map #define maii unordered_map<int, int, custom_hash> #define vc vector #define id1 int n; cin >> n; #define gls getline(cin, s) #define sinf 1e9 #define inf (int) 1e18 #define co cout << #define sp(i) setprecision(i) << #define f1(i, a) for (auto& i : a) #define f2(i, j, a) for (auto& [i, j] : a) #define f3(i, j, k, a) for (auto& [i, j, k] : a) #define be(s) s.begin(), s.end() #define rbe(s) s.rbegin(), s.rend() #define bb(s) s.begin(), s.begin() #define ctz(x) __builtin_ctzll(x) #define cb(x) __builtin_popcountll(x) #define ff(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end))) #define i128 __int128_t #define lb lower_bound #define ub upper_bound #define ook order_of_key #define fbo find_by_order #define fn function #define bs bitset #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef unsigned long long ull; typedef pair<int, string> pis; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<string> vs; typedef vector<double> vd; typedef vector<pair<int,int>> vp; typedef vector<vector<int>> vvi; #pragma GCC optimize("Ofast,unroll-loops") #ifdef LOCAL #include "debug_util.h" #else #define help(...) #define helpArray(...) #define io #define _time #define _siu #endif template<class T> using pq = priority_queue<T>; template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 >& p) { os << p.first << " " << p.second; return os;} template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) {is >> p.first >> p.second; return is;} template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) {os << v[i] << (i + 1 != v.size() ? " " : "");} return os;} template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is;} struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; template<class T> bool constexpr chmin(T &a, T b) { if (a > b) {a = b;return true;} return false; } template<class T> bool constexpr chmax(T &a, T b) { if (a < b) {a = b;return true;} return false; } // stable sort template <typename T> vector<int> argsort(const vector<T> &A) { vector<int> ans(sz(A)); iota(be(ans), 0); sort(be(ans), [&](int i, int j) { return (A[i] == A[j] ? i < j : A[i] < A[j]); }); return ans; } //64b long long lsb(long long x) { return x & -x;} long long msb(long long x) { return (1ll << (63-__builtin_clzll(x))) & x;} void onb(long long& x, int i) { x |= (1ll << i);} void offb(long long& x, int i) { x &= ~(1ll << i);} bool hb(long long x, int i) { return ((1ll << i) & x) != 0;} long long bit(long long x) { return 1ll << x;} void YES(bool t = 1) { cout << (t ? "YES" : "NO") << "\n"; } void NO(bool t = 1) { YES(!t); } void Yes(bool t = 1) { cout << (t ? "Yes" : "No") << "\n"; } void No(bool t = 1) { Yes(!t); } template<typename T> vector<pair<T, int>> pfy(vector<T>& f) { vector<pair<T, int>> v; for (int i = 0; i < f.size(); i++) { v.push_back({f[i], i}); } return v; } bool inrange(int i, int j, int limi, int limj) { return i >= 0 && i < limi && j >= 0 && j < limj; } typedef tuple<int,int,int> iii; vector<char> cao = {'C','D','H','S'}; int dr8[] = {0,-1,0, 1, 1, 1, -1, -1}; int dc8[] = {-1, 0, 1, 0, 1, -1, 1, -1}; //n,w,e,s int dr[] = {-1, 0, 0, 1}; int dc[] = {0,-1,1, 0}; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int rand(int l, int r) { uniform_int_distribution<int> uid(l, r); return uid(rng); } // Define a tree-based set with integer keys template <typename T> using Tee = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; struct union_find { vector<int> parent; vector<int> size; int components = 0; union_find(int n = -1) { if (n >= 0) init(n); } void init(int n) { parent.resize(n); iota(parent.begin(), parent.end(), 0); size.assign(n, 1); components = n; } int find(int x) { return x == parent[x] ? x : parent[x] = find(parent[x]); } bool unite(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (size[x] < size[y]) swap(x, y); size[x] += size[y]; parent[y] = x; components--; return true; } }; void sui() { int n,a,b; cin>>n>>a>>b; vi v(n); cin>>v; union_find uf(n); map<int,int> intervals; ff(i,0,n) { help(intervals); auto it = lb(be(v),v[i]+a); int idx = it-v.begin(); auto it2 = ub(be(v),v[i]+b); int idx2 = it2-v.begin(); if (idx != n) { uf.unite(i,idx); auto mit = intervals.ub(idx); if (mit == intervals.end()) { intervals[idx2] = idx; } else { auto [x,y] = *mit; intervals.erase(mit); intervals[idx2] = y; } } } f2(y,x,intervals) { rep(i,x,y-1) uf.unite(i,i+1); } ff(i,0,n) co uf.size[uf.find(i)] onn; } signed main() { cin.tie(NULL); ios_base::sync_with_stdio(false); auto start = std::chrono::high_resolution_clock::now(); io; int n = 1; // cin >> n; ff(i,0,n) sui(); _time; return 0; }