結果
問題 | No.1222 -101 |
ユーザー |
![]() |
提出日時 | 2020-09-04 22:25:37 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 343 ms / 2,000 ms |
コード長 | 7,004 bytes |
コンパイル時間 | 2,292 ms |
コンパイル使用メモリ | 214,100 KB |
最終ジャッジ日時 | 2025-01-14 05:57:35 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#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 HEREsigned 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;}