結果

問題 No.1222 -101
ユーザー Chanyuh
提出日時 2020-09-05 11:00:05
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 218 ms / 2,000 ms
コード長 6,522 bytes
コンパイル時間 3,060 ms
コンパイル使用メモリ 117,872 KB
実行使用メモリ 26,200 KB
最終ジャッジ日時 2024-11-27 22:48:42
合計ジャッジ時間 6,623 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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

#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<tuple>
#include<cassert>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define Per(i,sta,n) for(int i=n-1;i>=sta;i--)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct T{
int l,r,t;
T(){}
T(int l,int r,int t):l(l),r(r),t(t){}
};
struct E{
int to,c;
E(){}
E(int to,int c):to(to),c(c){}
};
int n,m,L[200010];
int cnt[200010],cnt2[200010];
vector<int> z;
vector<T> q1;
vector<E> G[200010];
vector<int> col;
bool flag=true;
template<int mod>
struct ModInt {
long long x;
ModInt() : x(0) {}
ModInt(long long y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
explicit operator int() const {return x;}
ModInt &operator+=(const ModInt &p) {
if((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator-=(const ModInt &p) {
if((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator*=(const ModInt &p) {
x = (int)(1LL * x * p.x % mod);
return *this;
}
ModInt &operator/=(const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt operator-() const { return ModInt(-x); }
ModInt operator+(const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator-(const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator*(const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator/(const ModInt &p) const { return ModInt(*this) /= p; }
bool operator==(const ModInt &p) const { return x == p.x; }
bool operator!=(const ModInt &p) const { return x != p.x; }
ModInt inverse() const{
int a = x, b = mod, u = 1, v = 0, t;
while(b > 0) {
t = a / b;
a -= t * b;
swap(a, b);
u -= t * v;
swap(u, v);
}
return ModInt(u);
}
ModInt power(long long p) const{
int a = x;
if (p==0) return 1;
if (p==1) return ModInt(a);
if (p%2==1) return (ModInt(a)*ModInt(a)).power(p/2)*ModInt(a);
else return (ModInt(a)*ModInt(a)).power(p/2);
}
ModInt power(const ModInt p) const{
return ((ModInt)x).power(p.x);
}
friend ostream &operator<<(ostream &os, const ModInt<mod> &p) {
return os << p.x;
}
friend istream &operator>>(istream &is, ModInt<mod> &a) {
long long x;
is >> x;
a = ModInt<mod>(x);
return (is);
}
};
using modint = ModInt<mod>;
template <typename T>
struct SegmentTree{
using F = function<T(T,T)>;
int n;
F f;//
T ti;//
vector<T> dat;
SegmentTree(){}
SegmentTree(F f,T ti):f(f),ti(ti){}
void init(int n_){//sizen_segtree
n=1;
while(n<n_) n<<=1;
dat.assign(n<<1,ti);
}
void build(const vector<T> &v){//vsegtreebuild
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]);
}
void set_val(int k,T x){//kx
dat[k+=n]=x;
while(k>>=1)
dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
}
T query(int a,int b){//[a,b)F
if(a>=b) return ti;
T vl=ti,vr=ti;
for(int l=a+n,r=b+n;l<r;l>>=1,r>>=1) {
if(l&1) vl=f(vl,dat[l++]);
if(r&1) vr=f(dat[--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,dat[k]);
return check(acc)?k-n:-1;
}
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);
}
T &operator [] (int i) {return dat[i+n];};
};
int comp(int x){
return lower_bound(z.begin(),z.end(),x)-z.begin();
}
void dfs(int s,int co){
//cout << s << " " << co << endl;
col[s]=co;
for(E e:G[s]){
int t=e.to,c=e.c;
if(col[t]==-1) dfs(t,(col[s]+c)%2);
else if((col[s]+c)%2!=col[t]){
flag=false;
}
}
}
void solve(){
cin >> n >> m;
rep(i,n+1){
L[i]=-1;
}
rep(i,m){
int l,r,t;cin >> l >> r >> t;
if(t!=0){
cnt[l]+=1;
cnt[r+1]-=1;
if(t==1)q1.push_back(T(l,r,0));
if(t==-1)q1.push_back(T(l,r,1));
}
else{
L[r]=l;
}
}
rep(i,n){
cnt[i+1]+=cnt[i];
cnt2[i+1]+=cnt2[i];
}
z.push_back(0);
rep(i,n+1){
if(cnt[i]) z.push_back(i);
}
int k=z.size();
for(T q:q1){
G[comp(q.l)-1].push_back(E(comp(q.r),q.t));
G[comp(q.r)].push_back(E(comp(q.l)-1,q.t));
}
col.resize(k,-1);
int num=0;
rep(i,k){
if(col[i]!=-1) continue;
dfs(i,0);
num+=1;
}
if(!flag){
cout << 0 << endl;
return;
}
//cout << num << endl;
int pos=0;
SegmentTree<modint> seg([](modint a,modint b){return a+b;},0);
seg.init(n+1);
seg.set_val(0,((modint)2).power(n));
int v=0;
rep(i,n){
if(cnt[i+1]==0) seg.set_val(i+1,seg.query(pos,i+1)/(modint)2);
else v+=1;
pos=max(pos,L[i+1]);
//cout << i+1 << " " << pos << " " << seg.query(i+1,i+2) << endl;
}
cout << seg.query(pos,n+1)/((modint)2).power(v-num+1) << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(50);
solve();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0