結果
問題 | No.1222 -101 |
ユーザー |
![]() |
提出日時 | 2020-09-05 02:52:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 942 ms / 2,000 ms |
コード長 | 2,771 bytes |
コンパイル時間 | 2,229 ms |
コンパイル使用メモリ | 185,168 KB |
実行使用メモリ | 15,104 KB |
最終ジャッジ日時 | 2024-11-27 03:25:06 |
合計ジャッジ時間 | 11,863 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#pragma GCC optimize ("O2")#pragma GCC target ("avx2")#include<bits/stdc++.h>using namespace std;typedef long long ll;#define rep(i, n) for(int i = 0; i < (n); i++)#define rep1(i, n) for(int i = 1; i <= (n); i++)#define co(x) cout << (x) << "\n"#define cosp(x) cout << (x) << " "#define ce(x) cerr << (x) << "\n"#define cesp(x) cerr << (x) << " "#define pb push_back#define mp make_pair#define chmin(x, y) x = min(x, y)#define chmax(x, y) x = max(x, y)#define Would#define you#define pleaseconst int K = 19;const int KM = 1 << (K - 1);ll dat[1 << K];ll laz1[1 << K];ll laz2[1 << K];const int mod = 1e9 + 7;void eval(int A, int l, int r) {if (A * 2 < 1 << K) {laz1[A * 2] = laz1[A * 2] * laz1[A] % mod;laz1[A * 2 + 1] = laz1[A * 2 + 1] * laz1[A] % mod;laz2[A * 2] = (laz2[A * 2] * laz1[A] + laz2[A]) % mod;laz2[A * 2 + 1] = (laz2[A * 2 + 1] * laz1[A] + laz2[A]) % mod;}dat[A] = (dat[A] * laz1[A] + laz2[A] * (r - l)) % mod;laz1[A] = 1;laz2[A] = 0;}ll update(int L, int R, ll X, ll Y, int A, int l, int r) {eval(A, l, r);if (r <= L || R <= l) return dat[A];if (L <= l && r <= R) {laz1[A] = X;laz2[A] = Y;return (dat[A] * laz1[A] + laz2[A] * (r - l)) % mod;}return dat[A] = (update(L, R, X, Y, A * 2, l, (l + r) / 2) + update(L, R, X, Y, A * 2 + 1, (l + r) / 2, r)) % mod;}void add(int L, int R, ll X, ll Y) {update(L, R, X, Y, 1, 0, KM);}ll check(int L, int R, int A, int l, int r) {eval(A, l, r);if (r <= L || R <= l) return 0;if (L <= l && r <= R) return dat[A];return (check(L, R, A * 2, l, (l + r) / 2) + check(L, R, A * 2 + 1, (l + r) / 2, r)) % mod;}ll query(int L, int R) {return check(L, R, 1, 0, KM);}int main() {cin.tie(0);ios::sync_with_stdio(false);int N, M;cin >> N >> M;int L[200200] = {};int P[200200];int kazu = 0;rep(i, M) {int l, r, p;cin >> l >> r >> p;L[r] = l;P[r] = p;if (p != 0) kazu++;}add(0, 1, 1, 1);int saidai = -1;const int mod = 1e9 + 7;int imos[200200] = {};int kazuimo = 0;for (int i = N; i >= 1; i--) {imos[i] += imos[i + 1];if (L[i]) {if (P[i] == 0) {chmax(saidai, L[i]);}else {imos[i]++;imos[L[i] - 1]--;}}if (imos[i] && saidai >= i) {co(0);return 0;}if (!imos[i]) {if (saidai != -1) {auto tmp = query(0, i + 1);auto tmp2 = query(0, L[i]);add(L[i], i + 1, 2, 0);add(0, L[i], 0, 0);add(0, 1, 1, tmp);add(L[i], L[i] + 1, 1, tmp2 * 2);saidai = -1;}else {auto tmp = query(0, i + 1);add(0, i + 1, 2, 0);add(0, 1, 1, tmp);}}else kazuimo++;}ll kotae = query(0, 1);rep(i, kazuimo - kazu) {kotae = kotae * 2 % mod;}co(kotae);Would you please return 0;}