結果
問題 | No.1222 -101 |
ユーザー |
![]() |
提出日時 | 2020-09-05 01:16:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 959 ms / 2,000 ms |
コード長 | 2,779 bytes |
コンパイル時間 | 3,220 ms |
コンパイル使用メモリ | 207,480 KB |
最終ジャッジ日時 | 2025-01-14 06:37:16 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include <bits/stdc++.h>using namespace std;typedef signed long long ll;#undef _P#define _P(...) (void)printf(__VA_ARGS__)#define FOR(x,to) for(x=0;x<(to);x++)#define FORR(x,arr) for(auto& x:arr)#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)#define ALL(a) (a.begin()),(a.end())#define ZERO(a) memset(a,0,sizeof(a))#define MINUS(a) memset(a,0xff,sizeof(a))//-------------------------------------------------------int N,M;int L[202020],R[202020],P[202020];int cand[202020];const ll mo=1000000007;template<class V,int NV> class SegTree_MulAdd {public:vector<V> sum,mul,add; // sum stores val after muladdSegTree_MulAdd(){sum.resize(NV*2,0); mul.resize(NV*2,1); add.resize(NV*2,0);};V getval(int x,int y,int l=0,int r=NV,int k=1) {if(r<=x || y<=l) return 0;if(x<=l && r<=y) return sum[k];x=max(x,l);y=min(y,r);V ret=getval(x,y,l,(l+r)/2,k*2)+getval(x,y,(l+r)/2,r,k*2+1);return (ret*mul[k]+add[k]*(y-x))%mo;}void propagate(int k,int s) {(mul[k*2]*=mul[k])%=mo;(add[k*2]*=mul[k])%=mo;(sum[k*2]*=mul[k])%=mo;(add[k*2]+=add[k])%=mo;(sum[k*2]+=add[k]*s%mo*(mo+1)/2)%=mo;(mul[k*2+1]*=mul[k])%=mo;(add[k*2+1]*=mul[k])%=mo;(sum[k*2+1]*=mul[k])%=mo;(add[k*2+1]+=add[k])%=mo;(sum[k*2+1]+=add[k]*s%mo*(mo+1)/2)%=mo;mul[k]=1;add[k]=0;}void domul(int x,int y,V v,int l=0,int r=NV,int k=1) {if(l>=r) return;if(x<=l && r<=y) {(mul[k]*=v)%=mo;(add[k]*=v)%=mo;(sum[k]*=v)%=mo;}else if(l < y && x < r) {propagate(k,r-l);domul(x,y,v,l,(l+r)/2,k*2);domul(x,y,v,(l+r)/2,r,k*2+1);sum[k]=(sum[k*2]+sum[k*2+1])%mo;}}void doadd(int x,int y,V v,int l=0,int r=NV,int k=1) {if(l>=r) return;if(x<=l && r<=y) {(add[k]+=v)%=mo;(sum[k]+=(r-l)*v)%=mo;}else if(l < y && x < r) {propagate(k,r-l);doadd(x,y,v/mul[k],l,(l+r)/2,k*2);doadd(x,y,v/mul[k],(l+r)/2,r,k*2+1);sum[k]=(sum[k*2]+sum[k*2+1])%mo;}}};SegTree_MulAdd<ll,1<<18> st;void solve() {int i,j,k,l,r,x,y; string s;MINUS(cand);cin>>N>>M;ll rev=(mo+1)/2;ll p=1;FOR(i,M) {cin>>L[i]>>R[i]>>P[i];cand[R[i]]=i;if(P[i]) p=p*rev%mo;}st.doadd(0,1,p);for(i=1;i<=N;i++) {if(cand[i]==-1) {ll v=st.getval(0,i);st.domul(0,i,2);st.doadd(i,i+1,v);}else if(P[cand[i]]==0) {ll v=st.getval(0,i);st.domul(0,i,2);st.doadd(i,i+1,v);st.domul(0,L[cand[i]],0);}else {st.domul(0,L[cand[i]],2);st.domul(L[cand[i]],i,0);}}ll v=st.getval(0,N+1);cout<<v%mo<<endl;}int main(int argc,char** argv){string s;int i;if(argc==1) ios::sync_with_stdio(false), cin.tie(0);FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);cout.tie(0); solve(); return 0;}