結果

問題 No.1222 -101
ユーザー Mister
提出日時 2020-09-04 22:38:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 110 ms / 2,000 ms
コード長 5,007 bytes
コンパイル時間 866 ms
コンパイル使用メモリ 97,896 KB
最終ジャッジ日時 2025-01-14 06:02:14
ジャッジサーバーID
(参考情報)
judge2 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>
template <int MOD>
struct ModInt {
using lint = long long;
int val;
// constructor
ModInt(lint v = 0) : val(v % MOD) {
if (val < 0) val += MOD;
};
// unary operator
ModInt operator+() const { return ModInt(val); }
ModInt operator-() const { return ModInt(MOD - val); }
ModInt inv() const { return this->pow(MOD - 2); }
// arithmetic
ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
ModInt pow(lint n) const {
auto x = ModInt(1);
auto b = *this;
while (n > 0) {
if (n & 1) x *= b;
n >>= 1;
b *= b;
}
return x;
}
// compound assignment
ModInt& operator+=(const ModInt& x) {
if ((val += x.val) >= MOD) val -= MOD;
return *this;
}
ModInt& operator-=(const ModInt& x) {
if ((val -= x.val) < 0) val += MOD;
return *this;
}
ModInt& operator*=(const ModInt& x) {
val = lint(val) * x.val % MOD;
return *this;
}
ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }
// compare
bool operator==(const ModInt& b) const { return val == b.val; }
bool operator!=(const ModInt& b) const { return val != b.val; }
bool operator<(const ModInt& b) const { return val < b.val; }
bool operator<=(const ModInt& b) const { return val <= b.val; }
bool operator>(const ModInt& b) const { return val > b.val; }
bool operator>=(const ModInt& b) const { return val >= b.val; }
// I/O
friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept {
lint v;
is >> v;
x = v;
return is;
}
friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};
template <class T>
struct SegmentTree {
using Merger = std::function<T(T, T)>;
int length;
std::vector<T> dat;
T unit;
Merger merge;
SegmentTree() = default;
SegmentTree(int n, const T& unit, const Merger& merge)
: length(1), unit(unit), merge(merge) {
while (length < n) length <<= 1;
dat.assign(length * 2, unit);
}
template <class Container>
SegmentTree(const Container& elems, const T& unit, const Merger& merge)
: length(1), unit(unit), merge(merge) {
int n = elems.size();
while (length < n) length <<= 1;
dat.assign(length * 2, unit);
std::copy(elems.begin(), elems.end(), dat.begin() + length);
for (int nidx = length - 1; nidx >= 1; --nidx) {
T vl = dat[nidx * 2 + 0];
T vr = dat[nidx * 2 + 1];
dat[nidx] = merge(vl, vr);
}
}
void update(int nidx, const T& elem) {
nidx += length;
dat[nidx] = elem;
while (nidx > 0) {
nidx >>= 1;
T vl = dat[nidx * 2 + 0];
T vr = dat[nidx * 2 + 1];
dat[nidx] = merge(vl, vr);
}
}
T fold(int ql, int qr) const {
ql = std::max(ql, 0);
qr = std::min(qr, length);
ql += length, qr += length;
T lacc = unit, racc = unit;
while (ql < qr) {
if (ql & 1) {
lacc = merge(lacc, dat[ql]);
++ql;
}
if (qr & 1) {
--qr;
racc = merge(dat[qr], racc);
}
ql >>= 1, qr >>= 1;
}
return merge(lacc, racc);
}
T get(int idx) const { return dat[idx + length]; }
T fold_all() const { return dat[1]; }
};
constexpr int MOD = 1000000007;
using mint = ModInt<MOD>;
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<int> nonzero(n + 2, 0);
int nonzq = 0;
std::vector<int> ls(n + 1, -1);
while (m--) {
int l, r, p;
std::cin >> l >> r >> p;
if (p != 0) {
++nonzero[l];
--nonzero[r + 1];
++nonzq;
} else {
ls[r] = l;
}
}
int nonze = 0;
for (int i = 1; i <= n; ++i) {
if (nonzero[i]) ++nonze;
nonzero[i + 1] += nonzero[i];
}
mint pz = mint(2).pow(nonze - nonzq);
SegmentTree<mint>
seg(n + 1, 0, [](auto a, auto b) { return a + b; });
seg.update(0, 1);
int l = 0, p = 0;
for (int i = 1; i <= n; ++i) {
if (nonzero[i] == 0) {
seg.update(i, seg.fold(l, i) / mint(2));
++p;
}
l = std::max(l, ls[i]);
}
mint po = seg.fold(l, n + 1) * mint(2).pow(p);
std::cout << pz * po << "\n";
}
int main() {
std::cin.tie(nullptr);
std::ios::sync_with_stdio(false);
solve();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0