結果

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

ソースコード

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

#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: odd
int 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0