結果

問題 No.1222 -101
ユーザー beet
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0