結果

問題 No.1222 -101
ユーザー uzzy
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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

#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 please
const 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0