結果
問題 | No.1222 -101 |
ユーザー |
![]() |
提出日時 | 2020-09-04 22:57:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 631 ms / 2,000 ms |
コード長 | 8,812 bytes |
コンパイル時間 | 1,674 ms |
コンパイル使用メモリ | 183,220 KB |
実行使用メモリ | 15,872 KB |
最終ジャッジ日時 | 2024-11-26 20:53:41 |
合計ジャッジ時間 | 10,442 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:243:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions] 243 | auto[R, L, P]=RLP[i]; | ^
ソースコード
#include <bits/stdc++.h>using namespace std;#define int long long#define rep(i, n) for (int i = 0; i < (int) (n); i++)#define reps(i, n) for (int i = 1; i <= (int) (n); i++)#define all(x) (x).begin(), (x).end()#define uniq(x) (x).erase(unique(all(x)), (x).end())#define bit(n) (1LL << (n))#define dump(x) cerr << #x " = " << (x) << endlusing vint = vector<int>;using vvint = vector<vint>;using pint = pair<int, int>;using vpint = vector<pint>;template<typename T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;constexpr double PI = 3.1415926535897932384626433832795028;constexpr int DY[9] = {0, 1, 0, -1, 1, 1, -1, -1, 0};constexpr int DX[9] = {1, 0, -1, 0, 1, -1, -1, 1, 0};int sign(int x) { return (x > 0) - (x < 0); }int gcd(int a, int b) {while (b) { swap(a %= b, b); }return a;}int lcm(int a, int b) { return a / gcd(a, b) * b; }int cdiv(int a, int b) { return (a - 1 + b) / b; }template<typename T> void fin(T mes) {cout << mes << endl;exit(0);}template<typename T, typename U> bool chmax(T &a, const U &b) {if (a < b) {a = b;return true;}return false;}template<typename T, typename U> bool chmin(T &a, const U &b) {if (b < a) {a = b;return true;}return false;}template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &rhs) {os << "(" << rhs.first << ", " << rhs.second << ")";return os;}template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {os << "{";for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {os << *itr << (next(itr) != rhs.end() ? ", " : "");}os << "}";return os;}template<typename T> ostream &operator<<(ostream &os, const deque<T> &rhs) {os << "{";for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {os << *itr << (next(itr) != rhs.end() ? ", " : "");}os << "}";return os;}template<typename T> ostream &operator<<(ostream &os, const set<T> &rhs) {os << "{";for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {os << *itr << (next(itr) != rhs.end() ? ", " : "");}os << "}";return os;}template<typename T, typename U> ostream &operator<<(ostream &os, const map<T, U> &rhs) {os << "{";for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {os << *itr << (next(itr) != rhs.end() ? ", " : "");}os << "}";return os;}struct setup {static constexpr int PREC = 20;setup() {cout << fixed << setprecision(PREC);cerr << fixed << setprecision(PREC);};} setup;template<int MOD = 1000000007>struct mod_int {int val;mod_int(long long val_ = 0) : val(val_ % MOD) { if (val < 0) { val += MOD; }}bool operator==(const mod_int &rhs) const { return val == rhs.val; }bool operator!=(const mod_int &rhs) const { return std::rel_ops::operator!=(*this, rhs); }mod_int &operator+=(const mod_int &rhs) {if ((val += rhs.val) >= MOD) { val -= MOD; }return *this;}mod_int &operator-=(const mod_int &rhs) {if ((val += MOD - rhs.val) >= MOD) { val -= MOD; }return *this;}mod_int &operator*=(const mod_int &rhs) {val = (int) ((long long) val * rhs.val % MOD);return *this;}mod_int &operator/=(const mod_int &rhs) { return *this *= rhs.inv(); }mod_int operator+() const { return *this; }mod_int operator-() const { return -val; }mod_int operator++() { return *this += 1; }mod_int operator--() { return *this -= 1; }mod_int operator++(signed) {const mod_int ret(*this);++*this;return ret;}mod_int operator--(signed) {const mod_int ret(*this);--*this;return ret;}mod_int operator+(const mod_int &rhs) const { return mod_int(*this) += rhs; }mod_int operator-(const mod_int &rhs) const { return mod_int(*this) -= rhs; }mod_int operator*(const mod_int &rhs) const { return mod_int(*this) *= rhs; }mod_int operator/(const mod_int &rhs) const { return mod_int(*this) /= rhs; }mod_int inv() const {assert(val != 0);int a = val, b = MOD, x = 1, u = 0;while (b) {int t = a / b;std::swap(a -= t * b, b);std::swap(x -= t * u, u);}return x;}mod_int pow(long long n) const {if (n < 0) { return pow(-n).inv(); }mod_int ret = 1, mul = *this;while (n) {if (n & 1) { ret *= mul; }mul *= mul;n >>= 1;}return ret;}friend std::istream &operator>>(std::istream &is, mod_int &rhs) {long long v;is >> v;rhs = v;return is;}friend std::ostream &operator<<(std::ostream &os, const mod_int &rhs) { return os << rhs.val; }struct combination {std::vector<mod_int> fact{1, 1}, f_inv{1, 1}, inv{0, 1};void calc(int n) {while (fact.size() <= n) {int i = fact.size();fact.push_back(fact[i - 1] * i);inv.push_back(-inv[MOD % i] * (MOD / i));f_inv.push_back(f_inv[i - 1] * inv[i]);}}mod_int P(int n, int r) { return r < 0 || n < r ? 0 : (calc(n), fact[n] * f_inv[n - r]); }mod_int C(int n, int r) { return r < 0 || n < r ? 0 : (calc(n), fact[n] * f_inv[r] * f_inv[n - r]); }mod_int H(int n, int r) { return C(n + r - 1, r); }};};using mint = mod_int<>;template<typename M>struct lazy_segment_tree {using T = typename M::T;using E = typename M::E;int n;std::vector<T> data;std::vector<E> lazy;lazy_segment_tree(int n) : n(n), data(n << 1, M::id_T()), lazy(n << 1, M::id_E()) {}lazy_segment_tree(const std::vector<T> &src) : n(src.size()), data(n << 1), lazy(n << 1, M::id_E()) {std::copy(src.begin(), src.end(), data.begin() + n);for (int i = n - 1; i > 0; i--) { data[i] = M::op_TT(data[i << 1 | 0], data[i << 1 | 1]); }}void propagate(int i) {if (i < 1) { return; }data[i] = M::op_TE(data[i], lazy[i]);if (i < n) {lazy[i << 1 | 0] = M::op_EE(lazy[i << 1 | 0], lazy[i]);lazy[i << 1 | 1] = M::op_EE(lazy[i << 1 | 1], lazy[i]);}lazy[i] = M::id_E();}void apply(int l, int r, const E &x) {l += n, r += n - 1;for (int i = std::__lg(r); i > 0; i--) {propagate(l >> i);propagate(r >> i);}auto update = [&](int i) { lazy[i] = M::op_EE(lazy[i], x), propagate(i); };for (int i = l, j = r + 1; i < j; i >>= 1, j >>= 1) {if (i & 1) { update(i++); }if (j & 1) { update(--j); }}while (l >>= 1, r >>= 1) {data[l] = M::op_TT(M::op_TE(data[l << 1 | 0], lazy[l << 1 | 0]),M::op_TE(data[l << 1 | 1], lazy[l << 1 | 1]));data[r] = M::op_TT(M::op_TE(data[r << 1 | 0], lazy[r << 1 | 0]),M::op_TE(data[r << 1 | 1], lazy[r << 1 | 1]));}}T fold(int l, int r) {l += n, r += n - 1;for (int i = std::__lg(r); i > 0; i--) { propagate(l >> i), propagate(r >> i); }T a = M::id_T(), b = M::id_T();for (r++; l < r; l >>= 1, r >>= 1) {if (l & 1) { propagate(l), a = M::op_TT(a, data[l++]); }if (r & 1) { propagate(--r), b = M::op_TT(data[r], b); }}return M::op_TT(a, b);}};struct rsq_and_rcq {using T = mint;using E = mint;static T id_T() { return 0; };static E id_E() { return 1; };static T op_TT(const T &a, const T &b) { return a + b; }static E op_EE(const E &a, const E &b) { return a * b; }static T op_TE(const T &a, const E &b) { return a * b; }};signed main() {int N, M;cin >> N >> M;vector<tuple<int, int, int>> RLP(M);rep(i, M) {int L, R, P;cin >> L >> R >> P;RLP[i] = {R, L, P};}sort(all(RLP));lazy_segment_tree<rsq_and_rcq> lst(vector<mint>(N + 1, 1));int last = 0;rep(i, M) {auto[R, L, P]=RLP[i];for (int j = last + 1; j < R; j++) {lst.apply(j, j + 1, lst.fold(0, j));lst.apply(0, j, 2);}last = R;if (P == 0) {lst.apply(R, R + 1, lst.fold(0, R));lst.apply(0, L, 0);lst.apply(L, R, 2);} else { lst.apply(L, R + 1, 0); }}for (int j = last + 1; j <= N; j++) {lst.apply(j, j + 1, lst.fold(0, j));lst.apply(0, j, 2);}cout << lst.fold(0, N + 1) << endl;}