結果
問題 | No.1222 -101 |
ユーザー |
![]() |
提出日時 | 2020-09-04 22:42:34 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 358 ms / 2,000 ms |
コード長 | 3,047 bytes |
コンパイル時間 | 3,129 ms |
コンパイル使用メモリ | 86,608 KB |
実行使用メモリ | 19,200 KB |
最終ジャッジ日時 | 2024-11-26 20:34:32 |
合計ジャッジ時間 | 8,564 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include <iostream>#include <cstdio>#include <cmath>#include <ctime>#include <cstdlib>#include <cassert>#include <vector>#include <list>#include <stack>#include <queue>#include <deque>#include <map>#include <set>#include <bitset>#include <string>#include <algorithm>#include <utility>#define llint long long#define inf 1e18#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)#define chmin(x, y) (x) = min((x), (y))#define chmax(x, y) (x) = max((x), (y))#define mod 1000000007using namespace std;// range-add, range-min querystruct LazySegTree{int size;vector<llint> seg, delay;LazySegTree(){}LazySegTree(int size){this->size = size;seg.resize(1<<(size+1));delay.resize(1<<(size+1));}void init(){for(int i = 0; i < (1<<(size+1)); i++){seg[i] = 0;delay[i] = 1;}}void eval(int l, int r, int k){if(delay[k] != 1){seg[k] *= delay[k], seg[k] %= mod; //総和クエリのときは区間幅を乗じる必要があるif(l < r){delay[k*2] *= delay[k], delay[k*2] %= mod;delay[k*2+1] *= delay[k], delay[k*2+1] %= mod;}delay[k] = 1;}}void update(int i, llint val){int l = 0, r = (1<<size)-1, k = 1;eval(l, r, k);for(int j = size-1; j >= 0; j--){k <<= 1;if(i & (1<<j)){k++;r = (l+r)/2;}else l = (l+r)/2+1;eval(l, r, k);}i += (1 << size);seg[i] = val;while(i > 1){i /= 2;seg[i] = (seg[i*2] + seg[i*2+1]) % mod;}}void add(int a, int b, int k, int l, int r, llint val){eval(l, r, k);if(b < l || r < a) return;if(a <= l && r <= b){delay[k] *= val, delay[k] %= mod;eval(l, r, k);return;}add(a, b, k*2, l, (l+r)/2, val);add(a, b, k*2+1, (l+r)/2+1, r, val);seg[k] = (seg[k*2] + seg[k*2+1]) % mod;}void add(int a, int b, llint val){if(a > b) return;add(a, b, 1, 0, (1<<size)-1, val);}llint query(int a, int b, int k, int l, int r){eval(l, r, k);if(b < l || r < a) return 0;if(a <= l && r <= b) return seg[k];llint lval = query(a, b, k*2, l, (l+r)/2);llint rval = query(a, b, k*2+1, (l+r)/2+1, r);return (lval + rval) % mod;}llint query(int a, int b){return query(a, b, 1, 0, (1<<size)-1);}};llint n, m;llint l[200005], r[200005], p[200005];llint L[200005], P[200005];LazySegTree seg(18);int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m;for(int i = 1; i <= m; i++){cin >> l[i] >> r[i] >> p[i];L[r[i]] = l[i], P[r[i]] = p[i];}seg.init();seg.update(0, 1);for(int i = 1; i <= n; i++){if(L[i] == 0){seg.update(i, seg.query(0, i-1));seg.add(0, i-1, 2);}else{if(P[i] == 0){seg.update(i, seg.query(0, i-1));seg.add(0, L[i]-1, 0);seg.add(L[i], i-1, 2);}else seg.add(L[i], i-1, 0);}//for(int i = 0; i <= n; i++) cout << seg.query(i, i) << " "; cout << endl;}llint ans = seg.query(0, n);cout << ans << endl;return 0;}