結果
問題 | No.1222 -101 |
ユーザー |
|
提出日時 | 2020-10-03 18:53:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 362 ms / 2,000 ms |
コード長 | 6,688 bytes |
コンパイル時間 | 2,468 ms |
コンパイル使用メモリ | 216,688 KB |
最終ジャッジ日時 | 2025-01-15 02:11:52 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i, n) for(int i = 0; i < n; i++)#define rep2(i, x, n) for(int i = x; i <= n; i++)#define rep3(i, x, n) for(int i = x; i >= n; i--)#define elif else if#define sp(x) fixed << setprecision(x)#define pb push_back#define eb emplace_back#define all(x) x.begin(), x.end()#define sz(x) (int)x.size()using ll = long long;using pii = pair<int, int>;using pil = pair<int, ll>;using pli = pair<ll, int>;using pll = pair<ll, ll>;const int MOD = 1000000007;//const int MOD = 998244353;const int inf = (1<<30)-1;const ll INF = (1LL<<60)-1;const double pi = acos(-1.0);const double EPS = 1e-10;template<typename T> bool chmax(T &x, const T &y) {return (x < y)? (x = y, true) : false;};template<typename T> bool chmin(T &x, const T &y) {return (x > y)? (x = y, true) : false;};template<int mod>struct Mod_Int{ll x;Mod_Int() : x(0) {}Mod_Int(ll y) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}Mod_Int &operator += (const Mod_Int &p){x = (x + p.x) % mod;return *this;}Mod_Int &operator -= (const Mod_Int &p){x = (x + mod - p.x) % mod;return *this;}Mod_Int &operator *= (const Mod_Int &p){x = (x * p.x) % mod;return *this;}Mod_Int &operator /= (const Mod_Int &p){*this *= p.inverse();return *this;}Mod_Int &operator ++ () {return *this += Mod_Int(1);}Mod_Int operator ++ (int){Mod_Int tmp = *this;++*this;return tmp;}Mod_Int &operator -- () {return *this -= Mod_Int(1);}Mod_Int operator -- (int){Mod_Int tmp = *this;--*this;return tmp;}Mod_Int operator - () const {return Mod_Int(-x);}Mod_Int operator + (const Mod_Int &p) const {return Mod_Int(*this) += p;}Mod_Int operator - (const Mod_Int &p) const {return Mod_Int(*this) -= p;}Mod_Int operator * (const Mod_Int &p) const {return Mod_Int(*this) *= p;}Mod_Int operator / (const Mod_Int &p) const {return Mod_Int(*this) /= p;}bool operator == (const Mod_Int &p) const {return x == p.x;}bool operator != (const Mod_Int &p) const {return x != p.x;}Mod_Int inverse() const {assert(*this != Mod_Int(0));return pow(mod-2);}Mod_Int pow(ll k) const{Mod_Int now = *this, ret = 1;while(k){if(k&1) ret *= now;now *= now, k >>= 1;}return ret;}friend ostream &operator << (ostream &os, const Mod_Int &p){return os << p.x;}friend istream &operator >> (istream &is, Mod_Int &p){ll a;is >> a;p = Mod_Int<mod>(a);return is;}};using mint = Mod_Int<MOD>;template<typename Monoid, typename Operator_Monoid>struct Lazy_Segment_Tree{vector<Monoid> seg;vector<Operator_Monoid> lazy;const Monoid e1;const Operator_Monoid e2;const int n;Monoid f(const Monoid &a, const Monoid &b) const{return {a.first+b.first, a.second+b.second};}Monoid g(const Monoid &a, const Operator_Monoid &b) const{return {a.first+b*a.second, a.second};}Operator_Monoid h(const Operator_Monoid &a, const Operator_Monoid &b) const{return a+b;}Lazy_Segment_Tree(const vector<Monoid> &v, const Monoid &e1, const Operator_Monoid &e2): e1(e1), e2(e2), n(1<<(32-__builtin_clz(sz(v)-1))){seg.assign(2*n, e1), lazy.assign(2*n, e2);copy(all(v), seg.begin()+n);rep3(i, n-1, 1) seg[i] = f(seg[2*i], seg[2*i+1]);}void eval(int i, int l, int r){if(lazy[i] != e2){seg[i] = g(seg[i], lazy[i]);if(r-l > 1){lazy[2*i] = h(lazy[2*i] ,lazy[i]);lazy[2*i+1] = h(lazy[2*i+1], lazy[i]);}lazy[i] = e2;}}void apply(int a, int b, const Operator_Monoid &x, int i, int l, int r){eval(i, l, r);if(a >= r || b <= l) return;if(a <= l && r <= b){lazy[i] = h(lazy[i], x);eval(i, l, r);}else{apply(a, b, x, 2*i, l, (l+r)/2);apply(a, b, x, 2*i+1, (l+r)/2, r);seg[i] = f(seg[2*i], seg[2*i+1]);}}void apply(int a, int b, const Operator_Monoid &x) {apply(a, b, x, 1, 0, n);}Monoid query(int a, int b, int i, int l, int r){eval(i, l, r);if(a >= r || b <= l) return e1;if(a <= l && r <= b) return seg[i];Monoid vl = query(a, b, 2*i, l, (l+r)/2);Monoid vr = query(a, b, 2*i+1, (l+r)/2, r);return f(vl, vr);}Monoid query(int a, int b) {return query(a, b, 1, 0, n);}void update(int i, int l, int r){seg[i] = g(seg[i], lazy[i]);if(r-l > 1){lazy[2*i] = h(lazy[2*i], lazy[i]);lazy[2*i+1] = h(lazy[2*i+1], lazy[i]);update(2*i, l, (l+r)/2);update(2*i+1, (l+r)/2, r);}lazy[i] = e2;}void update() {update(1, 0, n);}Monoid operator [] (int i) const {return seg[n+i];}};int main(){int N, M;cin >> N >> M;vector<pii> tmp;vector<int> rs(N, 0);rep(i, M){int l, r, p; cin >> l >> r >> p; l--;if(p == 0) tmp.eb(r, l);else chmax(rs[l], r);}vector<bool> zero(N, true);int ptr = 0;rep(i, N){chmax(ptr, rs[i]);if(ptr > i) zero[i] = false;}vector<int> rem;rep(i, N){if(zero[i]) rem.pb(i);}int n = sz(rem);mint ans = mint(2).pow(N-n-(M-sz(tmp)));for(auto &e: tmp){e.first = lower_bound(all(rem), e.first)-rem.begin();e.second = lower_bound(all(rem), e.second)-rem.begin();if(e.first == e.second) {cout << 0 << endl; return 0;}}sort(all(tmp));vector<int> query(n, -1);ptr = -1;for(auto &e: tmp){if(chmax(ptr, e.second)) query[e.second] = e.first;}vector<pair<mint, mint>> v(n+1);rep(i, n+1){v[i].first = 0;if(i == 0) v[i].second = 1, v[i].first = 1;else v[i].second = v[i-1].second*2;}Lazy_Segment_Tree<pair<mint, mint>, mint> seg(v, {0, 0}, 0);mint inv = mint(1)/mint(2);mint pw[n+1];pw[0] = 1;rep(i, n) pw[i+1] = pw[i]*inv;rep(i, n){mint tmp = seg.query(i, i+1).first;if(query[i] == -1) seg.apply(i+1, i+2, tmp*3*pw[i+1]);else seg.apply(i+1, query[i]+1, tmp*pw[i+1]);}ans *= seg.query(n, n+1).first;cout << ans << endl;}