#547824 (C++17) No.1222 -101

提出ソース

結果

問題	No.1222 -101
ユーザー	beet
提出日時	2020-09-04 22:25:37
言語	C++17 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	350 ms / 2,000 ms
コード長	7,004 bytes
コンパイル時間	2,486 ms
コンパイル使用メモリ	217,500 KB
実行使用メモリ	12,836 KB
最終ジャッジ日時	2023-08-17 17:02:22
合計ジャッジ時間	8,433 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 4,376 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	2 ms 4,376 KB
testcase_03	AC	1 ms 4,380 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	2 ms 4,380 KB
testcase_06	AC	1 ms 4,376 KB
testcase_07	AC	1 ms 4,376 KB
testcase_08	AC	1 ms 4,380 KB
testcase_09	AC	1 ms 4,376 KB
testcase_10	AC	261 ms 10,412 KB
testcase_11	AC	236 ms 10,476 KB
testcase_12	AC	230 ms 9,976 KB
testcase_13	AC	228 ms 10,132 KB
testcase_14	AC	230 ms 10,256 KB
testcase_15	AC	222 ms 11,468 KB
testcase_16	AC	222 ms 9,424 KB
testcase_17	AC	222 ms 9,980 KB
testcase_18	AC	222 ms 11,288 KB
testcase_19	AC	216 ms 9,012 KB
testcase_20	AC	213 ms 10,120 KB
testcase_21	AC	214 ms 9,992 KB
testcase_22	AC	2 ms 4,376 KB
testcase_23	AC	2 ms 4,376 KB
testcase_24	AC	2 ms 4,376 KB
testcase_25	AC	1 ms 4,380 KB
testcase_26	AC	1 ms 4,380 KB
testcase_27	AC	1 ms 4,376 KB
testcase_28	AC	1 ms 4,380 KB
testcase_29	AC	1 ms 4,380 KB
testcase_30	AC	1 ms 4,380 KB
testcase_31	AC	2 ms 4,380 KB
testcase_32	AC	350 ms 12,760 KB
testcase_33	AC	350 ms 12,836 KB
testcase_34	AC	137 ms 11,788 KB
testcase_35	AC	141 ms 11,660 KB
testcase_36	AC	118 ms 11,804 KB
testcase_37	AC	120 ms 11,712 KB
testcase_38	AC	120 ms 11,764 KB

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

ソースコード

raw source code

#include <bits/stdc++.h>
using namespace std;

using Int = long long;
const char newl = '\n';

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
template<typename T> void drop(const T &x){cout<<x<<endl;exit(0);}
template<typename T=int>
vector<T> read(size_t n){
  vector<T> ts(n);
  for(size_t i=0;i<n;i++) cin>>ts[i];
  return ts;
}


template<typename TV, const int N> void read_tuple_impl(TV&) {}
template<typename TV, const int N, typename Head, typename... Tail>
void read_tuple_impl(TV& ts) {
  get<N>(ts).emplace_back(*(istream_iterator<Head>(cin)));
  read_tuple_impl<TV, N+1, Tail...>(ts);
}
template<typename... Ts> decltype(auto) read_tuple(size_t n) {
  tuple<vector<Ts>...> ts;
  for(size_t i=0;i<n;i++) read_tuple_impl<decltype(ts), 0, Ts...>(ts);
  return ts;
}


template<typename T,T MOD = 1000000007>
struct Mint{
  static constexpr T mod = MOD;
  T v;
  Mint():v(0){}
  Mint(signed v):v(v){}
  Mint(long long t){v=t%MOD;if(v<0) v+=MOD;}

  Mint pow(long long k){
    Mint res(1),tmp(v);
    while(k){
      if(k&1) res*=tmp;
      tmp*=tmp;
      k>>=1;
    }
    return res;
  }

  static Mint add_identity(){return Mint(0);}
  static Mint mul_identity(){return Mint(1);}

  Mint inv(){return pow(MOD-2);}

  Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;}
  Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;}
  Mint& operator/=(Mint a){return (*this)*=a.inv();}

  Mint operator+(Mint a) const{return Mint(v)+=a;}
  Mint operator-(Mint a) const{return Mint(v)-=a;}
  Mint operator*(Mint a) const{return Mint(v)*=a;}
  Mint operator/(Mint a) const{return Mint(v)/=a;}

  Mint operator-() const{return v?Mint(MOD-v):Mint(v);}

  bool operator==(const Mint a)const{return v==a.v;}
  bool operator!=(const Mint a)const{return v!=a.v;}
  bool operator <(const Mint a)const{return v <a.v;}

  static Mint comb(long long n,int k){
    Mint num(1),dom(1);
    for(int i=0;i<k;i++){
      num*=Mint(n-i);
      dom*=Mint(i+1);
    }
    return num/dom;
  }
};
template<typename T,T MOD> constexpr T Mint<T, MOD>::mod;
template<typename T,T MOD>
ostream& operator<<(ostream &os,Mint<T, MOD> m){os<<m.v;return os;}




template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  int n,height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(F f,G g,H h,T ti,E ei):
    f(f),g(g),h(h),ti(ti),ei(ei){}

  void init(int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    dat.assign(2*n,ti);
    laz.assign(2*n,ei);
  }

  void build(const vector<T> &v){
    int n_=v.size();
    init(n_);
    for(int i=0;i<n_;i++) dat[n+i]=v[i];
    for(int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }

  inline T reflect(int k){
    return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
  }

  inline void propagate(int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    dat[k]=reflect(k);
    laz[k]=ei;
  }

  inline void thrust(int k){
    for(int i=height;i;i--) propagate(k>>i);
  }

  inline void recalc(int k){
    while(k>>=1)
      dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
  }

  void update(int a,int b,E x){
    if(a>=b) return;
    thrust(a+=n);
    thrust(b+=n-1);
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
    recalc(a);
    recalc(b);
  }

  void set_val(int a,T x){
    thrust(a+=n);
    dat[a]=x;laz[a]=ei;
    recalc(a);
  }

  T query(int a,int b){
    if(a>=b) return ti;
    thrust(a+=n);
    thrust(b+=n-1);
    T vl=ti,vr=ti;
    for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,reflect(l++));
      if(r&1) vr=f(reflect(--r),vr);
    }
    return f(vl,vr);
  }

  template<typename C>
  int find(int st,C &check,T &acc,int k,int l,int r){
    if(l+1==r){
      acc=f(acc,reflect(k));
      return check(acc)?k-n:-1;
    }
    propagate(k);
    int m=(l+r)>>1;
    if(m<=st) return find(st,check,acc,(k<<1)|1,m,r);
    if(st<=l&&!check(f(acc,dat[k]))){
      acc=f(acc,dat[k]);
      return -1;
    }
    int vl=find(st,check,acc,(k<<1)|0,l,m);
    if(~vl) return vl;
    return find(st,check,acc,(k<<1)|1,m,r);
  }

  template<typename C>
  int find(int st,C &check){
    T acc=ti;
    return find(st,check,acc,1,0,n);
  }
};


struct UnionFind{
  int num;
  vector<int> rs,ps;
  UnionFind(){}
  UnionFind(int n):num(n),rs(n,1),ps(n,0){iota(ps.begin(),ps.end(),0);}
  int find(int x){
    return (x==ps[x]?x:ps[x]=find(ps[x]));
  }
  bool same(int x,int y){
    return find(x)==find(y);
  }
  void unite(int x,int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(rs[x]<rs[y]) swap(x,y);
    rs[x]+=rs[y];
    ps[y]=x;
    num--;
  }
  int size(int x){
    return rs[find(x)];
  }
  int count() const{
    return num;
  }
};

//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n,m;
  cin>>n>>m;
  auto [ls,rs,ps]=read_tuple<int, int, int>(m);

  for(int &l:ls) l--;

  vector<int> zs(n+1);
  for(int i=0;i<m;i++){
    if(ps[i]==0) continue;
    zs[ls[i]]++;
    zs[rs[i]]--;
  }
  for(int i=1;i<=n;i++) zs[i]+=zs[i-1];

  vector<int> xs,ys;
  for(int i=0;i<n;i++){
    if(zs[i]==0) xs.emplace_back(i);
    else ys.emplace_back(i);
  }

  using M = Mint<int>;
  auto solve1=[&]()->M{
    M res{0};
    int s=xs.size();
    vector<int> qs(s+1,-1);
    for(int i=0;i<m;i++){
      if(ps[i]!=0) continue;
      if(s==0) return M(0);
      int l=lower_bound(xs.begin(),xs.end(),ls[i])-xs.begin();
      int r=lower_bound(xs.begin(),xs.end(),rs[i])-xs.begin();
      chmax(qs[r],l);
    }

    auto f=[&](M a,M b){return a+b;};
    auto g=[&](M a,M b){return a*b;};
    M ti(0),ei(1);
    SegmentTree<M, M> seg(f,g,g,ti,ei);
    seg.build(vector<M>(s,0));

    vector<M> dp(s+1);
    for(int i=0;i<s;i++){
      dp[i]=M(qs[i]<0?2:0).pow(i);
      dp[i]+=seg.query(max<int>(qs[i],0),i);
      seg.set_val(i,dp[i]);
      seg.update(0,i,M(2));
      chmax(qs[i+1],qs[i]);
    }
    dp[s]=M(qs[s]<0?2:0).pow(s);
    dp[s]+=seg.query(max<int>(qs[s],0),s);
    return dp[s];
  };

  auto solve2=[&]()->M{
    int s=ys.size();
    UnionFind uf(2*(s+1));
    UnionFind cn(s+1);
    for(int i=0;i<m;i++){
      if(ps[i]==0) continue;
      int l=lower_bound(ys.begin(),ys.end(),ls[i])-ys.begin();
      int r=lower_bound(ys.begin(),ys.end(),rs[i])-ys.begin();
      if(ps[i]==+1){
        uf.unite(l,r);
        uf.unite(s+1+l,s+1+r);
      }
      if(ps[i]==-1){
        uf.unite(l,s+1+r);
        uf.unite(s+1+l,r);
      }
      if(uf.same(l,s+1+l)) return M(0);
      if(uf.same(r,s+1+r)) return M(0);
      cn.unite(l,r);
    }
    return M(2).pow(cn.count()-1);
  };
  // cout<<solve1()<<':'<<solve2()<<newl;
  cout<<solve1()*solve2()<<newl;
  return 0;
}

yukicoder

結果

テストケース

ソースコード