結果
問題 | No.1222 -101 |
ユーザー |
|
提出日時 | 2020-09-04 22:50:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 550 ms / 2,000 ms |
コード長 | 15,324 bytes |
コンパイル時間 | 4,083 ms |
コンパイル使用メモリ | 322,288 KB |
最終ジャッジ日時 | 2025-01-14 06:15:07 |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#pragma region kyopro_template#define Nyaan_template#include <immintrin.h>#include <bits/stdc++.h>#define pb push_back#define eb emplace_back#define fi first#define se second#define each(x, v) for (auto &x : v)#define all(v) (v).begin(), (v).end()#define sz(v) ((int)(v).size())#define mem(a, val) memset(a, val, sizeof(a))#define ini(...) \int __VA_ARGS__; \in(__VA_ARGS__)#define inl(...) \long long __VA_ARGS__; \in(__VA_ARGS__)#define ins(...) \string __VA_ARGS__; \in(__VA_ARGS__)#define inc(...) \char __VA_ARGS__; \in(__VA_ARGS__)#define in2(s, t) \for (int i = 0; i < (int)s.size(); i++) { \in(s[i], t[i]); \}#define in3(s, t, u) \for (int i = 0; i < (int)s.size(); i++) { \in(s[i], t[i], u[i]); \}#define in4(s, t, u, v) \for (int i = 0; i < (int)s.size(); i++) { \in(s[i], t[i], u[i], v[i]); \}#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)#define reg(i, a, b) for (long long i = (a); i < (b); i++)#define die(...) \do { \out(__VA_ARGS__); \return; \} while (0)using namespace std;using ll = long long;template <class T>using V = vector<T>;using vi = vector<int>;using vl = vector<long long>;using vvi = vector<vector<int>>;using vd = V<double>;using vs = V<string>;using vvl = vector<vector<long long>>;using P = pair<long long, long long>;using vp = vector<P>;using pii = pair<int, int>;using vpi = vector<pair<int, int>>;constexpr int inf = 1001001001;constexpr long long infLL = (1LL << 61) - 1;template <typename T, typename U>inline bool amin(T &x, U y) {return (y < x) ? (x = y, true) : false;}template <typename T, typename U>inline bool amax(T &x, U y) {return (x < y) ? (x = y, true) : false;}template <typename T, typename U>ostream &operator<<(ostream &os, const pair<T, U> &p) {os << p.first << " " << p.second;return os;}template <typename T, typename U>istream &operator>>(istream &is, pair<T, U> &p) {is >> p.first >> p.second;return is;}template <typename T>ostream &operator<<(ostream &os, const vector<T> &v) {int s = (int)v.size();for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];return os;}template <typename T>istream &operator>>(istream &is, vector<T> &v) {for (auto &x : v) is >> x;return is;}void in() {}template <typename T, class... U>void in(T &t, U &... u) {cin >> t;in(u...);}void out() { cout << "\n"; }template <typename T, class... U>void out(const T &t, const U &... u) {cout << t;if (sizeof...(u)) cout << " ";out(u...);}#ifdef NyaanDebug#define trc(...) \do { \cerr << #__VA_ARGS__ << " = "; \dbg_out(__VA_ARGS__); \} while (0)#define trca(v, N) \do { \cerr << #v << " = "; \array_out(v, N); \} while (0)#define trcc(v) \do { \cerr << #v << " = {"; \each(x, v) { cerr << " " << x << ","; } \cerr << "}" << endl; \} while (0)template <typename T>void _cout(const T &c) {cerr << c;}void _cout(const int &c) {if (c == 1001001001)cerr << "inf";else if (c == -1001001001)cerr << "-inf";elsecerr << c;}void _cout(const unsigned int &c) {if (c == 1001001001)cerr << "inf";elsecerr << c;}void _cout(const long long &c) {if (c == 1001001001 || c == (1LL << 61) - 1)cerr << "inf";else if (c == -1001001001 || c == -((1LL << 61) - 1))cerr << "-inf";elsecerr << c;}void _cout(const unsigned long long &c) {if (c == 1001001001 || c == (1LL << 61) - 1)cerr << "inf";elsecerr << c;}template <typename T, typename U>void _cout(const pair<T, U> &p) {cerr << "{ ";_cout(p.fi);cerr << ", ";_cout(p.se);cerr << " } ";}template <typename T>void _cout(const vector<T> &v) {int s = v.size();cerr << "{ ";for (int i = 0; i < s; i++) {cerr << (i ? ", " : "");_cout(v[i]);}cerr << " } ";}template <typename T>void _cout(const vector<vector<T>> &v) {cerr << "[ ";for (const auto &x : v) {cerr << endl;_cout(x);cerr << ", ";}cerr << endl << " ] ";}void dbg_out() { cerr << endl; }template <typename T, class... U>void dbg_out(const T &t, const U &... u) {_cout(t);if (sizeof...(u)) cerr << ", ";dbg_out(u...);}template <typename T>void array_out(const T &v, int s) {cerr << "{ ";for (int i = 0; i < s; i++) {cerr << (i ? ", " : "");_cout(v[i]);}cerr << " } " << endl;}template <typename T>void array_out(const T &v, int H, int W) {cerr << "[ ";for (int i = 0; i < H; i++) {cerr << (i ? ", " : "");array_out(v[i], W);}cerr << " ] " << endl;}#else#define trc(...)#define trca(...)#define trcc(...)#endifinline int popcnt(unsigned long long a) { return __builtin_popcountll(a); }inline int lsb(unsigned long long a) { return __builtin_ctzll(a); }inline int msb(unsigned long long a) { return 63 - __builtin_clzll(a); }template <typename T>inline int getbit(T a, int i) {return (a >> i) & 1;}template <typename T>inline void setbit(T &a, int i) {a |= (1LL << i);}template <typename T>inline void delbit(T &a, int i) {a &= ~(1LL << i);}template <typename T>int lb(const vector<T> &v, const T &a) {return lower_bound(begin(v), end(v), a) - begin(v);}template <typename T>int ub(const vector<T> &v, const T &a) {return upper_bound(begin(v), end(v), a) - begin(v);}template <typename T>int btw(T a, T x, T b) {return a <= x && x < b;}template <typename T, typename U>T ceil(T a, U b) {return (a + b - 1) / b;}constexpr long long TEN(int n) {long long ret = 1, x = 10;while (n) {if (n & 1) ret *= x;x *= x;n >>= 1;}return ret;}template <typename T>vector<T> mkrui(const vector<T> &v) {vector<T> ret(v.size() + 1);for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];return ret;};template <typename T>vector<T> mkuni(const vector<T> &v) {vector<T> ret(v);sort(ret.begin(), ret.end());ret.erase(unique(ret.begin(), ret.end()), ret.end());return ret;}template <typename F>vector<int> mkord(int N, F f) {vector<int> ord(N);iota(begin(ord), end(ord), 0);sort(begin(ord), end(ord), f);return ord;}template <typename T = int>vector<T> mkiota(int N) {vector<T> ret(N);iota(begin(ret), end(ret), 0);return ret;}template <typename T>vector<int> mkinv(vector<T> &v) {vector<int> inv(v.size());for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i;return inv;}struct IoSetupNya {IoSetupNya() {cin.tie(nullptr);ios::sync_with_stdio(false);cout << fixed << setprecision(15);cerr << fixed << setprecision(7);}} iosetupnya;void solve();int main() { solve(); }#pragma endregionusing namespace std;template <uint32_t mod>struct LazyMontgomeryModInt {using mint = LazyMontgomeryModInt;using i32 = int32_t;using u32 = uint32_t;using u64 = uint64_t;static constexpr u32 get_r() {u32 ret = mod;for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret;return ret;}static constexpr u32 r = get_r();static constexpr u32 n2 = -u64(mod) % mod;static_assert(r * mod == 1, "invalid, r * mod != 1");static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30");static_assert((mod & 1) == 1, "invalid, mod % 2 == 0");u32 a;constexpr LazyMontgomeryModInt() : a(0) {}constexpr LazyMontgomeryModInt(const int64_t &b): a(reduce(u64(b % mod + mod) * n2)){};static constexpr u32 reduce(const u64 &b) {return (b + u64(u32(b) * u32(-r)) * mod) >> 32;}constexpr mint &operator+=(const mint &b) {if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod;return *this;}constexpr mint &operator-=(const mint &b) {if (i32(a -= b.a) < 0) a += 2 * mod;return *this;}constexpr mint &operator*=(const mint &b) {a = reduce(u64(a) * b.a);return *this;}constexpr mint &operator/=(const mint &b) {*this *= b.inverse();return *this;}constexpr mint operator+(const mint &b) const { return mint(*this) += b; }constexpr mint operator-(const mint &b) const { return mint(*this) -= b; }constexpr mint operator*(const mint &b) const { return mint(*this) *= b; }constexpr mint operator/(const mint &b) const { return mint(*this) /= b; }constexpr bool operator==(const mint &b) const {return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a);}constexpr bool operator!=(const mint &b) const {return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a);}constexpr mint operator-() const { return mint() - mint(*this); }constexpr mint pow(u64 n) const {mint ret(1), mul(*this);while (n > 0) {if (n & 1) ret *= mul;mul *= mul;n >>= 1;}return ret;}constexpr mint inverse() const { return pow(mod - 2); }friend ostream &operator<<(ostream &os, const mint &b) {return os << b.get();}friend istream &operator>>(istream &is, mint &b) {int64_t t;is >> t;b = LazyMontgomeryModInt<mod>(t);return (is);}constexpr u32 get() const {u32 ret = reduce(a);return ret >= mod ? ret - mod : ret;}static constexpr u32 get_mod() { return mod; }};using namespace std;// LazySegmentTreetemplate <typename T, typename E, typename F, typename G, typename H>struct LST {int n, height;F f;G g;H h;T ti;E ei;vector<T> dat;vector<E> laz;LST(int n, F f, G g, H h, T ti, E ei) : f(f), g(g), h(h), ti(ti), ei(ei) {init(n);}LST(const vector<T> &v, F f, G g, H h, T ti, E ei): f(f), g(g), h(h), ti(ti), ei(ei) {init((int)v.size());build(v);}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 eval(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--) eval(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) {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) {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);}};using namespace std;template <typename E, E UNUSED_VALUE>struct UpdateSum_LazySegmentTree {int n, height;using T = pair<E, E>;T f(T a, T b) { return T(a.first + b.first, a.second + b.second); };T g(T a, E b) { return T(b * a.second, a.second); };E h(E, E b) { return b; };T ti = P(0, 0);E ei = UNUSED_VALUE;vector<T> dat;vector<E> laz;UpdateSum_LazySegmentTree(const vector<E> &v) { build(v); }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<E> &v) {int n_ = v.size();init(n_);for (int i = 0; i < n_; i++) dat[n + i] = T(v[i], 1);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);}E query(int a, int b) {if (a >= b) return ti.first;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).first;}};void solve() {ini(N, M);vi L(M), R(M), P(M);in3(L, R, P);each(x, L) x--;using mint = LazyMontgomeryModInt<1000000007>;{UpdateSum_LazySegmentTree<int, -1> seg(vi(N, 0));rep(i, M) {if (P[i] != 0) seg.update(L[i], R[i], 1);}rep(i, M) {if (P[i] != 0) continue;if (seg.query(L[i], R[i]) == R[i] - L[i]) die(0);}}auto ord = mkord(M, [&](int i, int j) { return R[i] < R[j]; });auto f = [](mint a, mint b) { return a + b; };auto g = [](mint a, mint b) { return a * b; };auto h = [](mint a, mint b) { return a * b; };vector<mint> sini(N + 1);sini[0] = 1;LST<mint, mint, decltype(f), decltype(g), decltype(h)> lseg(sini, f, g, h, 0,1);int id = 0;each(i, ord) {trc(i, id);if (P[i] != 0) {while (id < R[i]) {++id;if (id <= L[i]) lseg.set_val(id, lseg.query(0, id));lseg.update(0, id, mint(2));}lseg.update(L[i] + 1, R[i] + 1, mint(0));rep(i, N + 1) trc(lseg.query(i, i + 1));continue;}while (id < R[i]) {++id;lseg.set_val(id, lseg.query(0, id));lseg.update(0, id, mint(2));}lseg.update(0, L[i] + 1, mint(0));rep(i, N + 1) trc(lseg.query(i, i + 1));}while (id < N) {++id;lseg.set_val(id, lseg.query(0, id));lseg.update(0, id, mint(2));}int nonzero = 0;each(p, P) nonzero += (p != 0);mint ans = lseg.query(0, N + 1) * mint(2).inverse().pow(nonzero);out(ans);}