結果

問題 No.1222 -101
ユーザー msm1993msm1993
提出日時 2020-10-08 10:05:49
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 146 ms / 2,000 ms
コード長 4,471 bytes
コンパイル時間 660 ms
コンパイル使用メモリ 53,116 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2024-07-20 05:47:33
合計ジャッジ時間 4,803 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 35 ms
9,344 KB
testcase_11 AC 35 ms
9,472 KB
testcase_12 AC 108 ms
9,344 KB
testcase_13 AC 108 ms
9,344 KB
testcase_14 AC 109 ms
9,344 KB
testcase_15 AC 73 ms
9,088 KB
testcase_16 AC 91 ms
9,216 KB
testcase_17 AC 101 ms
9,088 KB
testcase_18 AC 70 ms
9,088 KB
testcase_19 AC 78 ms
8,960 KB
testcase_20 AC 93 ms
8,960 KB
testcase_21 AC 91 ms
9,088 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 1 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 2 ms
5,376 KB
testcase_31 AC 1 ms
5,376 KB
testcase_32 AC 146 ms
11,520 KB
testcase_33 AC 144 ms
11,520 KB
testcase_34 AC 77 ms
11,520 KB
testcase_35 AC 75 ms
11,648 KB
testcase_36 AC 64 ms
8,448 KB
testcase_37 AC 66 ms
7,936 KB
testcase_38 AC 66 ms
9,728 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0