結果
問題 | No.1222 -101 |
ユーザー |
|
提出日時 | 2020-09-05 18:32:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 4,471 bytes |
コンパイル時間 | 595 ms |
コンパイル使用メモリ | 53,236 KB |
実行使用メモリ | 11,648 KB |
最終ジャッジ日時 | 2024-11-29 04:51:13 |
合計ジャッジ時間 | 4,540 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#include<cstdio>#include<algorithm>const long long mod = 1e9+7;struct Element{int l,r,t;Element(){}Element(int l,int r,int t):l(l),r(r),t(t){}};Element a[200005];Element b[200005];Element c[200005];//i: even, i+n+1: oddint p[400005];int isOne[200005];int fix[400005];int seq[200005];int border[200005];long long f[200005], prefix[200005];long long pow2[200005];int find(int u){if(p[u]==u) return u;else return p[u] = find(p[u]);}void merge(int x,int y){p[find(y)] = find(x);}long long cal(int n,int m){//printf("n = %d, m = %d\n",n,m);for(int i = 0; i <= 2*n+2; i++) p[i] = i, fix[i] = 0;for(int i = 1; i <= m; i++){int x = c[i].l-1, y = c[i].r;if(c[i].t==1) merge(x,y), merge(x+n+1,y+n+1);else merge(x,y+n+1), merge(x+n+1,y);}int x = find(0), y = find(0+n+1);fix[x] = fix[y] = 1;long long res = 1;for(int i = 1; i <= n; i++){if(find(i)==find(i+n+1)) res = 0;int x = find(i), y = find(i+n+1);if(!fix[x]){fix[x] = fix[y] = 1;res = res*2ll%mod;}}//printf("res = %lld\n",res);return res;}long long getPartOne(int n){std::sort(a+1,a+1+n,[&](Element& u,Element& v){return u.l<v.l;});long long res = 1;int p = 1;while(p<=n){int np = p, left = a[p].l, right = a[p].r;while(np+1<=n && a[np+1].l<=right){np++;if(right<a[np].r) right = a[np].r;}int size = 0;for(int i = p; i <= np; i++){c[++size] = a[i];c[size].l -= (left-1);c[size].r -= (left-1);}for(int i = left; i <= right; i++) isOne[i] = 1;res = res*cal(right-left+1,size)%mod;p = np+1;}return res;}int getFirst(int u,int n){int L = 1, R = n;int res = -1;while(L<=R){int M = (L+R)/2;if(seq[M]>=u){res = M;R = M-1;}else L = M+1;}return res;}int getLast(int u,int n){int L = 1, R = n;int res = -1;while(L<=R){int M = (L+R)/2;if(seq[M]<=u){res = M;L = M+1;}else R = M-1;}return res;}long long power(long long a,long long b){long long res = 1;while(b){if(b%2) res = res*a%mod;a = a*a%mod;b /= 2;}return res;}long long inv(long long u){ return power(u,mod-2); }long long getPartTwo(int n,int m){int size = 0;for(int i = 1; i <= n; i++){if(!isOne[i]) seq[++size] = i;}pow2[0] = 1;for(int i = 1; i <= size+2; i++) pow2[i] = pow2[i-1]*2ll%mod;for(int i = 1; i <= m; i++){int l = getFirst(b[i].l,size), r = getLast(b[i].r,size);if(l==-1 || r==-1 || l>r) return 0;else b[i].l = l, b[i].r = r;//printf("l = %d, r = %d\n",b[i].l,b[i].r);}std::sort(b+1,b+1+m,[&](Element& u,Element& v){return u.r<v.r;});int p = 0; int upper = 0;for(int i = 1; i <= size+1; i++){while(p+1<=m && b[p+1].r<i){p++;if(upper<b[p].l) upper = b[p].l;}border[i] = upper;}long long res = 0;f[0] = 1; prefix[0] = f[0]*inv(pow2[0+1])%mod;if(0>=upper){long long add = f[0]*pow2[size-0]%mod;res += add; if(res>=mod) res -= mod;}for(int i = 1; i <= size; i++){f[i] = prefix[i-1];if(border[i]!=0) f[i] -= prefix[border[i]-1];//printf("before: %lld\n",f[i]);if(f[i]<0) f[i] += mod;f[i] = f[i]*pow2[i]%mod;prefix[i] = prefix[i-1]+f[i]*inv(pow2[i+1])%mod; if(prefix[i]>=mod) prefix[i] -= mod;if(i>=upper){long long add = f[i]*pow2[size-i]%mod;res += add; if(res>=mod) res -= mod;}//printf("border[%d] = %d, f[%d] = %lld\n",i,border[i],i,f[i]);}return res;}int main(){int n,m;scanf("%d%d",&n,&m);int size0 = 0, size1 = 0;for(int i = 1; i <= m; i++){int l,r,t;scanf("%d%d%d",&l,&r,&t);if(t!=0) a[++size0] = Element(l,r,t);else b[++size1] = Element(l,r,t);}long long part1 = getPartOne(size0);//printf("%lld\n",part1);long long part2 = getPartTwo(n,size1);//printf("%lld\n",part2);printf("%lld\n",part1*part2%mod);return 0;}