#796732 (C++17) No.1170 Never Want to Walk

提出ソース

結果

問題	No.1170 Never Want to Walk
ユーザー	hari64
提出日時	2022-09-12 17:36:49
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	315 ms / 2,000 ms
コード長	14,274 bytes
コンパイル時間	2,955 ms
コンパイル使用メモリ	230,564 KB
実行使用メモリ	6,288 KB
最終ジャッジ日時	2023-08-19 21:18:33
合計ジャッジ時間	9,336 ms
ジャッジサーバーID （参考情報）	judge10 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,384 KB
testcase_01	AC	2 ms 4,384 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	1 ms 4,380 KB
testcase_04	AC	1 ms 4,380 KB
testcase_05	AC	2 ms 4,380 KB
testcase_06	AC	1 ms 4,380 KB
testcase_07	AC	2 ms 4,380 KB
testcase_08	AC	2 ms 4,380 KB
testcase_09	AC	2 ms 4,384 KB
testcase_10	AC	2 ms 4,380 KB
testcase_11	AC	2 ms 4,380 KB
testcase_12	AC	3 ms 4,384 KB
testcase_13	AC	3 ms 4,384 KB
testcase_14	AC	3 ms 4,380 KB
testcase_15	AC	3 ms 4,384 KB
testcase_16	AC	3 ms 4,380 KB
testcase_17	AC	3 ms 4,380 KB
testcase_18	AC	3 ms 4,384 KB
testcase_19	AC	3 ms 4,380 KB
testcase_20	AC	3 ms 4,384 KB
testcase_21	AC	3 ms 4,384 KB
testcase_22	AC	4 ms 4,380 KB
testcase_23	AC	3 ms 4,384 KB
testcase_24	AC	3 ms 4,380 KB
testcase_25	AC	3 ms 4,380 KB
testcase_26	AC	3 ms 4,380 KB
testcase_27	AC	298 ms 5,840 KB
testcase_28	AC	296 ms 5,900 KB
testcase_29	AC	313 ms 6,260 KB
testcase_30	AC	306 ms 6,204 KB
testcase_31	AC	294 ms 5,856 KB
testcase_32	AC	292 ms 5,940 KB
testcase_33	AC	289 ms 6,016 KB
testcase_34	AC	303 ms 6,288 KB
testcase_35	AC	302 ms 6,200 KB
testcase_36	AC	297 ms 6,020 KB
testcase_37	AC	297 ms 5,964 KB
testcase_38	AC	315 ms 6,284 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>  // clang-format off
using namespace std;constexpr int INF=1001001001;constexpr long long INFll=1001001001001001001;namespace viewer{using s=string;template<class T>s f(T i){s S=i==INF||i==INFll?"inf":to_string(i);return s(max(0,3-int(S.size())),' ')+S;}
template<class T>auto v(T&x,s&&e)->decltype(cerr<<x){return cerr<<x<<e;}void v(int x,s&&e){cerr<<f(x)<<e;}void v(long long x,s&&e){cerr<<f(x)<<e;}void v(float x,s&&e){cerr<<fixed<<setprecision(5)<<x<<e;}void v(double x,s&&e){cerr<<fixed<<setprecision(5)<<x<<e;}void v(long double x,s&&e){cerr<<fixed<<setprecision(5)<<x<<e;}
template<class T,class U>void v(const pair<T,U>&p,s&&e="\n"){cerr<<"(";v(p.first,", ");v(p.second,")"+e);}template<class T,class U>void v(const tuple<T,U>&t,s&&e="\n"){cerr<<"(";v(get<0>(t),", ");v(get<1>(t),")"+e);}template<class T,class U,class V>void v(const tuple<T,U,V>&t,s&&e="\n"){cerr<<"(";v(get<0>(t),", ");v(get<1>(t),", ");v(get<2>(t),")"+e);}template<class T,class U,class V,class W>void v(const tuple<T,U,V,W>&t,s&&e="\n"){cerr<<"(";v(get<0>(t),", ");v(get<1>(t),", ");v(get<2>(t),", ");v(get<3>(t),")"+e);}
template<class T>void v(const vector<T>&vx,s);template<class T>auto ve(int,const vector<T>&vx)->decltype(cerr<<vx[0]){cerr<<"{";for(const T&x:vx)v(x,",");return cerr<<"}\n";}template<class T>auto ve(bool,const vector<T>&vx){cerr<<"{\n";for(const T&x:vx)cerr<<"  ",v(x,",");cerr<<"}\n";}template<class T>void v(const vector<T>&vx,s){ve(0,vx);}
template<class T>void v(const deque<T>&q,s&&e){v(vector<T>(q.begin(),q.end()),e);}template<class T,class C>void v(const set<T,C>&S,s&&e){v(vector<T>(S.begin(),S.end()),e);}template<class T,class C>void v(const multiset<T,C>&S,s&&e){v(vector<T>(S.begin(),S.end()),e);}template<class T>void v(const unordered_set<T>&S,s&&e){v(vector<T>(S.begin(),S.end()),e);}
template<class T,class U,class V>void v(const priority_queue<T,U,V>&p,s&&e){priority_queue<T,U,V>q=p;vector<T>z;while(!q.empty()){z.push_back(q.top());q.pop();}v(z,e);}template<class T,class U>void v(const map<T,U>&m,s&&e){cerr<<"{"<<(m.empty()?"":"\n");for(const auto&kv:m){cerr<<"  [";v(kv.first,"");cerr<<"] : ";v(kv.second,"");cerr<<"\n";}cerr<<"}"+e;}
template<class T>void _view(int n,s&S,T&var){cerr<<"\033[1;32m"<<n<<"\033[0m: \033[1;36m"<<S<<"\033[0m = ";v(var,"\n");}template<class T>void grid(T _){}void grid(const vector<vector<bool>>&vvb){cerr<<"\n";for(const vector<bool>&vb:vvb){for(const bool&b:vb)cerr<<(b?".":"#");cerr<<"\n";}}
void _debug(int,s){}template<typename H,typename... T>void _debug(int n,s S,const H&h,const T&... t){int i=0,cnt=0;for(;i<int(S.size());i++){if(S[i]=='(')cnt++;if(S[i]==')')cnt--;if(cnt==0&&S[i]==',')break;}if(i==int(S.size()))_view(n,S,h);else{s S1=S.substr(0,i),S2=S.substr(i+2);if(S2=="\"grid\""){cerr<<"\033[1;32m"<<n<<"\033[0m: \033[1;36m"<<S1<<"\033[0m = ";grid(h);}else _view(n,S1,h),_debug(n,S2,t...);}}}
template<class T>bool chmax(T&a,const T&b){return a<b?a=b,1:0;}template<class T>bool chmin(T&a,const T&b){return a>b?a=b,1:0;} // https://rsk0315.hatenablog.com/entry/2021/01/18/065720
namespace internal{template<class T>using is_signed_int128=typename conditional<is_same<T,__int128_t>::value||is_same<T,__int128>::value,true_type,false_type>::type;template<class T>using is_unsigned_int128=typename conditional<is_same<T,__uint128_t>::value||is_same<T,unsigned __int128>::value,true_type,false_type>::type;template<class T>using is_integral=typename conditional<std::is_integral<T>::value||is_signed_int128<T>::value||is_unsigned_int128<T>::value,true_type,false_type>::type;
template<class T>using is_signed_int=typename conditional<(is_integral<T>::value&&is_signed<T>::value)||is_signed_int128<T>::value,true_type,false_type>::type;template<class T>using is_unsigned_int=typename conditional<(is_integral<T>::value&&is_unsigned<T>::value)||is_unsigned_int128<T>::value,true_type,false_type>::type;template<class T>using is_signed_int_t=enable_if_t<is_signed_int<T>::value>;template<class T>using is_unsigned_int_t=enable_if_t<is_unsigned_int<T>::value>;
constexpr long long safe_mod(long long x,long long m){x%=m;if(x<0)x+=m;return x;}struct barrett{unsigned int _m;unsigned long long im;explicit barrett(unsigned int m):_m(m),im((unsigned long long)(-1)/m+1){}unsigned int umod()const{return _m;}unsigned int mul(unsigned int a,unsigned int b)const{unsigned long long z=a;z*=b;unsigned long long x=(unsigned long long)(((unsigned __int128)(z)*im)>>64);unsigned int v=(unsigned int)(z-x*_m);if(_m<=v)v+=_m;return v;}};
constexpr long long pow_mod_constexpr(long long x,long long n,int m){if(m==1)return 0;unsigned int _m=(unsigned int)(m);unsigned long long r=1;unsigned long long y=safe_mod(x,m);while(n){if(n&1)r=(r*y)%_m;y=(y*y)%_m;n>>=1;}return r;}constexpr pair<long long,long long>inv_gcd(long long a,long long b){a=safe_mod(a,b);if(a==0)return{b,0};long long s=b,t=a;long long m0=0,m1=1;while(t){long long u=s/t;s-=t*u;m0-=m1*u;auto tmp=s;s=t;t=tmp;tmp=m0;m0=m1;m1=tmp;}if(m0<0)m0+=b/s;return{s,m0};}
constexpr bool is_prime_constexpr(int n){if(n<=1)return false;if(n==2||n==7||n==61)return true;if(n%2==0)return false;long long d=n-1;while(d%2==0)d/=2;constexpr long long bases[3]={2,7,61};for(long long a:bases){long long t=d;long long y=pow_mod_constexpr(a,t,n);while(t!=n-1&&y!=1&&y!=n-1){y=y*y%n;t<<=1;}if(y!=n-1&&t%2==0)return false;}return true;}template<int n>constexpr bool is_prime=is_prime_constexpr(n);} // namespace internal
template<int m>struct static_modint{using mint=static_modint;static constexpr int mod(){return m;}static mint raw(int v){mint x;x._v=v;return x;}static_modint():_v(0){}template<class T,internal::is_signed_int_t<T>* =nullptr>static_modint(T v){long long x=(long long)(v%(long long)(umod()));if(x<0)x+=umod();_v=(unsigned int)(x);}template<class T,internal::is_unsigned_int_t<T>* =nullptr>static_modint(T v){_v=(unsigned int)(v%umod());}unsigned int val()const{return _v;}
mint&operator++(){_v++;if(_v==umod())_v=0;return*this;}mint&operator--(){if(_v==0)_v=umod();_v--;return*this;}mint operator++(int){mint result=*this;++*this;return result;}mint operator--(int){mint result=*this;--*this;return result;}mint&operator+=(const mint&rhs){_v+=rhs._v;if(_v>=umod())_v-=umod();return*this;}mint&operator-=(const mint&rhs){_v-=rhs._v;if(_v>=umod())_v+=umod();return*this;}
mint&operator*=(const mint&rhs){unsigned long long z=_v;z*=rhs._v;_v=(unsigned int)(z%umod());return*this;}mint&operator/=(const mint&rhs){return*this=*this*rhs.inv();}mint operator+()const{return*this;}mint operator-()const{return mint()-*this;}mint pow(long long n)const{assert(0<=n);mint x=*this,r=1;while(n){if(n&1)r*=x;x*=x;n>>=1;}return r;}mint inv()const{if(prime){assert(_v);return pow(umod()-2);}else{auto eg=internal::inv_gcd(_v,m);assert(eg.first==1);return eg.second;}}
friend mint operator+(const mint&lhs,const mint&rhs){return mint(lhs)+=rhs;}friend mint operator-(const mint&lhs,const mint&rhs){return mint(lhs)-=rhs;}friend mint operator*(const mint&lhs,const mint&rhs){return mint(lhs)*=rhs;}friend mint operator/(const mint&lhs,const mint&rhs){return mint(lhs)/=rhs;}friend bool operator==(const mint&lhs,const mint&rhs){return lhs._v==rhs._v;}friend bool operator!=(const mint&lhs,const mint&rhs){return lhs._v!=rhs._v;}
friend ostream&operator<<(ostream&os,const mint&rhs){return os<<rhs._v;}friend istream&operator>>(istream&is,mint&rhs){long long v;is>>v;v%=(long long)(umod());if(v<0)v+=umod();;rhs._v=(unsigned int)v;return is;}static constexpr bool prime=internal::is_prime<m>;private:unsigned int _v;static constexpr unsigned int umod(){return m;}};
constexpr int MOD = 998244353;using mint=static_modint<MOD>;vector<mint>mint_factorial={mint(1)};/*n>1e8 ⇒ fast_modfact(deprecated)*/mint modfact(int n){assert(n<=100000000);if(int(mint_factorial.size())<=n){for(int i=mint_factorial.size();i<=n;i++){mint next=mint_factorial.back()*i;mint_factorial.push_back(next);}}return mint_factorial[n];}
/*x s.t. x^2 ≡ a (mod Prime) or -1*/mint modsqrt(mint a){long long p=mint::mod();if(a.val()==1)return a;if(a.pow((p-1)>>1).val()!=1)return -1;mint b=1,one=1;while(b.pow((p-1)>>1).val()==1)b+=one;long long m=p-1,e=0;while(m%2==0)m>>=1,e++;mint x=a.pow((m-1)>>1);mint y=a*x*x;x*=a;mint z=b.pow(m);while(y!=1){long long j=0;mint t=y;while(t!=one)j++,t*=t;z=z.pow(1ll<<(e-j-1));x*=z;z*=z;y*=z;e=j;}return x;}mint nCk(int n,int k){if(k<0||n<k)return mint(0);return modfact(n)*(modfact(k)).inv()*modfact(n-k).inv();}
/*min x s.t. a^x ≡ b (mod M) or -1*/int modlog(mint a,mint b){if(gcd(a.mod(),a.val())!=1){cout<<"\033[1;31mCAUTION: m must be coprime to a.\033[0m"<<endl;assert(false);}long long m=mint::mod();long long sq=round(sqrt(m))+1;unordered_map<long long,long long>ap;mint re=a;for(long long r=1;r<sq;r++){if(ap.find(re.val())==ap.end())ap[re.val()]=r;re*=a;}mint A=a.inv().pow(sq);re=b;for(mint q=0;q.val()<sq;q++){if(re==1&&q!=0)return(q*sq).val();if(ap.find(re.val())!=ap.end())return(q*sq+ap[re.val()]).val();re*=A;}return-1;};
#ifndef hari64
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define debug(...)
#else
#define debug(...) viewer::_debug(__LINE__, #__VA_ARGS__, __VA_ARGS__)
#endif  // clang-format on

// clang-format off
// Implement (union by size) + (path compression)
// Reference: Zvi Galil and Giuseppe F. Italiano,
struct UnionFind {
    explicit UnionFind(int n):_n(n),group_cnt(n),par_or_sz(n,-1),edge(n,0){}
    // the leader of the connected component
    virtual int merge(int a,int b){assert(0<=a&&a<_n&&0<=b&&b<_n);int x=find(a),y=find(b);if(x==y){edge[x]++;return x;};group_cnt--;if(-par_or_sz[x]<-par_or_sz[y])swap(x,y);edge[x]+=edge[y]+1;par_or_sz[x]+=par_or_sz[y];return par_or_sz[y]=x;}
    // the size of the connected component that contains the vertex a
    virtual int find(int a){assert(0<=a&&a<_n);return par_or_sz[a]<0?a:par_or_sz[a]=find(par_or_sz[a]);}
    // is same
    bool same(int a,int b){assert(0<=a&&a<_n&&0<=b&&b<_n);return find(a)==find(b);}
    // the size of the connected component that contains the vertex a
    int size(int a){assert(0<=a&&a<_n);return -par_or_sz[find(a)];}
    // cycle ⇒ -sz[a] <= -sz[a] - 1 = edge[a] (O(1)) / if a==-1 then check all vertexes (O(N))
    bool has_cycle(int a=-1){assert(-1<=a&&a<_n);if(0<=a){a=find(a);return -par_or_sz[a]<=edge[a];}else{for(int b=0;b<_n;b++)if(par_or_sz[b]<0&&-par_or_sz[b]<=edge[b])return true;}return false;}
    // tree ⇒ -sz[a] > -sz[a] - 1 = edge[a] O(N)
    int num_of_tree(){int num_of_tree=0;for(int a=0;a<_n;a++)if(par_or_sz[a]<0&&-par_or_sz[a]>edge[a])num_of_tree++;return num_of_tree;}
    // the list of the "list of the vertices in a connected component" O(N)
    vector<vector<int>>groups(bool index1=false){vector<vector<int>>ret(_n);for(int i=0;i<_n;i++)ret[find(i)].push_back(i+int(index1));ret.erase(remove_if(ret.begin(),ret.end(),[&](const vector<int>&v){return v.empty();}),ret.end());return ret;}
    // UnionFind::groups().size() O(1)
    int group_count(){return group_cnt;}
   protected:
    int _n;int group_cnt;/* root node: -1 * component size , otherwise: parent */vector<int>par_or_sz;vector<int>edge;
};

/// @ref https://qiita.com/drken/items/cce6fc5c579051e64fab
/// @brief merge(a,b,w): A[a] - A[b] == z
///        diff(a,b):  A[b]-A[a] (REQUIRE:same(a,b))
template <class Abel> struct weighted_dsu : UnionFind {
    explicit weighted_dsu(int n,Abel SUM_UNITY=0):diff_weight(n,SUM_UNITY){_n=n;group_cnt=0;par_or_sz.resize(n,-1);}
    int find(int a)override{assert(0<=a&&a<_n);if(par_or_sz[a]<0)return a;int r=find(par_or_sz[a]);diff_weight[a]+=diff_weight[par_or_sz[a]];return par_or_sz[a]=r;}
    int merge(int a,int b,Abel w){assert(0<=a&&a<_n&&0<=b&&b<_n);w+=weight(a)-weight(b);int x=find(a),y=find(b);if(x==y)return x;group_cnt--;if(-par_or_sz[x]<-par_or_sz[y])swap(x,y),w=-w;par_or_sz[x]+=par_or_sz[y];diff_weight[y]=w;return par_or_sz[y]=x;}
    Abel weight(int a){find(a);return diff_weight[a];}
    Abel diff(int a, int b){assert(same(a,b));return weight(b)-weight(a);}
    private:vector<Abel> diff_weight;};

/// @ref https://misteer.hatenablog.com/entry/persistentUF
/// @ref https://ei1333.github.io/library/structure/union-find/partially-persistent-union-find.cpp
/// @brief UnionFind which can reference all previous versions and update the current (not previous) version.
/// @note t = -1 is the initial time.(each node's parent is itself)
struct partially_persistent_dsu {
    partially_persistent_dsu(int n):_n(n),par_or_sz(n,-1),last(n,INF),add(n,{{-1,-1}}){}
    int merge(int a,int b,int t){assert(0<=a&&a<_n&&0<=b&&b<_n);int x=find(a,t),y=find(b,t);if(x==y)return x;if(-par_or_sz[x]<-par_or_sz[y])swap(x,y);last[y]=t;par_or_sz[x]+=par_or_sz[y];add[x].emplace_back(t,par_or_sz[x]);return par_or_sz[y]=x;}
    int find(int a,int t){assert(0<=a&&a<_n);if(t<last[a])return a;return find(par_or_sz[a],t);}
    bool same(int a,int b,int t){assert(0<=a&&a<_n&&0<=b&&b<_n);return find(a,t)==find(b,t);}
    int size(int a,int t){assert(0<=a&&a<_n);int x=find(a,t);return -prev(lower_bound(add[x].begin(),add[x].end(),make_pair(t,0)))->second;}
    private:int _n;vector<int>par_or_sz;vector<int>last;vector<vector<pair<int,int>>>add;};
// clang-format on

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, A, B;
    cin >> N >> A >> B;
    vector<int> Xs(N);
    for (int i = 0; i < N; i++) {
        cin >> Xs[i];
    }

    UnionFind uf(N);

    vector<int> imos(N);
    for (int i = 0; i < N - 1; i++) {
        int idx_l =
            distance(Xs.begin(), lower_bound(Xs.begin(), Xs.end(), Xs[i] + A));
        int idx_r =
            distance(Xs.begin(), lower_bound(Xs.begin(), Xs.end(), Xs[i] + B));
        if (idx_l == N) {
            continue;
        }
        if (idx_r < N && Xs[idx_r] == Xs[i] + B) {
            idx_r++;
        }
        debug(idx_l, idx_r);
        if (idx_l < idx_r) {
            uf.merge(i, idx_l);
            imos[idx_l]++;
            imos[--idx_r]--;
        }
    }

    int imos_sum = 0;
    for (int i = 0; i < N - 1; i++) {
        imos_sum += imos[i];
        if (imos_sum) {
            uf.merge(i, i + 1);
        }
    }

    debug(imos);

    debug(uf.groups());
    for (int i = 0; i < N; i++) {
        cout << uf.size(i) << endl;
    }

    return 0;
}

yukicoder

結果

テストケース

ソースコード