結果
問題 | No.1222 -101 |
ユーザー |
![]() |
提出日時 | 2020-09-04 23:46:31 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 192 ms / 2,000 ms |
コード長 | 4,442 bytes |
コンパイル時間 | 3,086 ms |
コンパイル使用メモリ | 204,956 KB |
最終ジャッジ日時 | 2025-01-14 06:30:27 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:190:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 190 | scanf("%d %d %d",&L[i],&R[i],&P[i]); | ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define modulo 1000000007#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)#define Inf 1000000000000000000template <typename T0,typename T1,typename F0,typename F1,typename F2>struct lazysegtree{//元データx[i]はv[n+i]//v[i]の親はv[i/2],子はv[i*2]とv[i*2+1]F0 func0;F1 func1;F2 func2;vector<T0> v0;vector<T1> v1;int n;int cnt;T0 init_value0;T1 init_value1;lazysegtree(int sz,F0 f0,F1 f1,F2 f2,T0 iv0,T1 iv1):func0(f0),func1(f1),func2(f2){init_value0 = iv0;init_value1 = iv1;n=1;cnt=0;while(true){if(n>=sz)break;n*=2;cnt++;}v0.resize(2*n,init_value0);v1.resize(2*n,init_value1);}lazysegtree(vector<T0> &x,F0 f0,F1 f1,F2 f2,T0 iv0,T1 iv1):func0(f0),func1(f1),func2(f2){init_value0 = iv0;init_value1 = iv1;n=1;cnt=0;while(true){if(n>=x.size())break;n*=2;cnt++;}v0.resize(2*n,init_value0);v1.resize(2*n,init_value1);for(int i=0;i<x.size();i++){v0[n+i]=x[i];}for(int i=n-1;i>=0;i--){v0[i]=func0(v0[i<<1],v0[(i<<1)+1]);}}//2人の子供に伝えるvoid propagate(int ind){update(ind<<1,v1[ind]);update((ind<<1)+1,v1[ind]);v1[ind] = init_value1;}//あるノードに対し先祖から伝播void reflect(int l,int r){int j = cnt;while(l>>j==r>>j&&j>=1){propagate(l>>j);j--;}for(;j>=1;j--){propagate(l>>j);propagate(r>>j);}}//子供の値を親に伝えるvoid mergeChildren(int ind){v0[ind] = func1(func0(v0[ind<<1],v0[(ind<<1)+1]),v1[ind],n>>(31-__builtin_clz(ind)));}//ある要素について作用させるvoid update(int ind,T1 x){v0[ind] = func1(v0[ind],x,n>>(31-__builtin_clz(ind)));v1[ind] = func2(v1[ind],x);}//[l,r)に対して作用させるvoid update(int l,int r,T1 x){if(l>=r)return;int L = l,R = r;l+=n;r+=n;reflect(l,r-1);while(true){if(l&1){update(l,x);l++;}if(r&1){update(r-1,x);r--;}if(l>=r)break;l>>=1;r>>=1;}l = L + n;r = R + n-1;while(true){l>>=1;r>>=1;if(l<=0)break;if(l==r){while(true){mergeChildren(l);l>>=1;if(!l)return;}}else{mergeChildren(l);mergeChildren(r);}}}//区間[l,r)におけるクエリ処理T0 query(int l,int r){T0 res1 = init_value0;T0 res2 = init_value0;if(l>=r)return res1;l+=n;r+=n;reflect(l,r-1);while(true){if(l&1){res1=func0(res1,v0[l]);l++;}if(r&1){res2=func0(v0[r-1],res2);r--;}if(l>=r)break;l>>=1;r>>=1;}return func0(res1,res2);}void show(){int n = 1;for(int i=1;i<v0.size();i++){for(int j=0;j<n;j++){if(j!=0)cout<<' ';cout<<v0[i+j];}cout<<endl;i+=n-1;n*=2;}}};int beki(long long a,long long b,int M = modulo){int x = 1;while(b!=0){if(b&1){x=((long long)x*a)%M;}a=((long long)a*a)%M;b>>=1;}return x;}int main(){int N,M;cin>>N>>M;vector<int> L(M),R(M),P(M);for(int i=0;i<M;i++){scanf("%d %d %d",&L[i],&R[i],&P[i]);L[i]--;R[i]--;}vector<int> imos0(N+1,0),imos1(N+1,0),f(N+1,0);for(int i=0;i<M;i++){if(P[i]==0){imos1[L[i]]++;imos1[R[i]+1]--;}else{imos0[L[i]]++;imos0[R[i]+1]--;f[R[i]]=1;}}for(int i=1;i<N;i++){imos0[i]+=imos0[i-1];imos1[i]+=imos1[i-1];}int ans = 1;vector<int> Z;for(int i=0;i<N;i++){int a = imos0[i],b = imos1[i];if(a==0&&b==0)ans = mod(ans * 3);else if(a>0){if(f[i]==0)ans = mod(ans * 2);}else{Z.push_back(i);}}vector<pair<int,int>> X;for(int i=0;i<M;i++){if(P[i]==0){L[i] = distance(Z.begin(),lower_bound(Z.begin(),Z.end(),L[i]));R[i] = distance(Z.begin(),upper_bound(Z.begin(),Z.end(),R[i]));R[i]--;if(L[i]>R[i]){cout<<0<<endl;return 0;}X.emplace_back(R[i],L[i]);}}sort(X.begin(),X.end());int p = 0;int l = 0;vector<int> dp(Z.size()+1,0);dp[0] = 1;int sum = 1;for(int i=1;i<=Z.size();i++){dp[i] = sum;sum = mod(sum * 2);if(p!=X.size() && X[p].first==i-1){while(l<=X[p].second){sum = mod(sum - mod(beki(2,i-l) * dp[l]));l++;}p++;}sum = mod(sum + dp[i]);}ans = mod(ans * sum);cout<<ans<<endl;return 0;}