結果

問題 No.1222 -101
ユーザー pockynypockyny
提出日時 2020-09-07 21:39:56
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 299 ms / 2,000 ms
コード長 4,014 bytes
コンパイル時間 1,263 ms
コンパイル使用メモリ 103,120 KB
実行使用メモリ 23,380 KB
最終ジャッジ日時 2023-08-19 17:12:34
合計ジャッジ時間 6,882 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,512 KB
testcase_01 AC 2 ms
5,404 KB
testcase_02 AC 3 ms
7,444 KB
testcase_03 AC 3 ms
7,516 KB
testcase_04 AC 2 ms
7,448 KB
testcase_05 AC 3 ms
7,444 KB
testcase_06 AC 2 ms
7,444 KB
testcase_07 AC 3 ms
7,444 KB
testcase_08 AC 2 ms
7,468 KB
testcase_09 AC 2 ms
5,400 KB
testcase_10 AC 148 ms
21,128 KB
testcase_11 AC 144 ms
20,932 KB
testcase_12 AC 234 ms
18,072 KB
testcase_13 AC 234 ms
17,908 KB
testcase_14 AC 235 ms
17,856 KB
testcase_15 AC 158 ms
19,160 KB
testcase_16 AC 198 ms
18,484 KB
testcase_17 AC 226 ms
17,732 KB
testcase_18 AC 158 ms
18,764 KB
testcase_19 AC 176 ms
17,996 KB
testcase_20 AC 202 ms
17,788 KB
testcase_21 AC 199 ms
17,864 KB
testcase_22 AC 2 ms
7,500 KB
testcase_23 AC 2 ms
5,488 KB
testcase_24 AC 2 ms
7,512 KB
testcase_25 AC 2 ms
7,544 KB
testcase_26 AC 2 ms
7,468 KB
testcase_27 AC 2 ms
5,612 KB
testcase_28 AC 3 ms
7,476 KB
testcase_29 AC 2 ms
7,684 KB
testcase_30 AC 2 ms
7,768 KB
testcase_31 AC 1 ms
5,376 KB
testcase_32 AC 297 ms
23,380 KB
testcase_33 AC 299 ms
23,260 KB
testcase_34 AC 184 ms
13,024 KB
testcase_35 AC 183 ms
12,960 KB
testcase_36 AC 163 ms
12,876 KB
testcase_37 AC 164 ms
13,148 KB
testcase_38 AC 161 ms
12,888 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
int par[400010],sz[400010];
void init(int n){
	for(int i=0;i<n;i++){
		par[i] = i; sz[i] = 1;
	}
}

int find(int x){
	if(par[x]==x) return x;
	return par[x] = find(par[x]);
}

void unite(int x, int y){
	x = find(x); y = find(y);
	if(x==y) return;
	if(sz[x]>sz[y]) swap(x,y);
	par[x] = y;
	sz[y] += sz[x];
}

bool same(int x, int y){
	return find(x)==find(y);
}

ll mod = 1000000007;
ll pw(ll a, ll x){
    ll ret = 1;
    while(x){
        if(x&1) (ret *= a) %= mod;
        (a *= a) %= mod; x /= 2;
    }
    return ret;
}

int cnt[200010] = {},ind[200010] = {};
vector<int> z,nz;
vector<pair<pair<int,int>,int>> v[2];
map<int,int> mp;
ll dp[200010],sum[200010];
int main(){
    int i,n,m; cin >> n >> m;
    for(i=0;i<m;i++){
        int l,r,p; cin >> l >> r >> p;
        if(p==0) v[0].push_back({{l,r},0});
        else{
            v[1].push_back({{l,r},p});
            cnt[l]++; cnt[r + 1]--;
        }
    }
    for(i=0;i<n;i++) cnt[i + 1] += cnt[i];
    nz.push_back(0);
    for(i=0;i<=n;i++){
        if(!cnt[i]) z.push_back(i);
        else nz.push_back(i);
    }
    z.push_back(n + 1);
    for(auto &p:v[0]){
        int l = p.first.first,r = p.first.second;
        int k = z[lower_bound(z.begin(),z.end(),l) - z.begin()];
        if(k>r){
            cout << 0 << endl;
            return 0;
        }
        l = k;
        r = z[upper_bound(z.begin(),z.end(),r) - z.begin() - 1];
        p = {{r,l},0};
    }
    sort(v[0].begin(),v[0].end());
    for(auto p:v[0]) ind[p.first.first + 1] = max(ind[p.first.first + 1],p.first.second);
    for(i=1;i<=n + 1;i++) ind[i] = max(ind[i],ind[i - 1]);
    ll inv = (mod + 1)/2;
    dp[0] = 1; sum[0] = 0; mp[0] = 0;
    /*set<int> s;
    for(i=1;i<z.size();i++) s.insert(z[i]);
    for(i=1;i<=n;i++){
        sum[i] = (sum[i - 1] + dp[i - 1])%mod;
        dp[i] = inv*(sum[i] - sum[ind[i]] + mod)%mod;
        if(!s.count(i)) dp[i] = 0;
    }*/
    for(i=1;i<z.size();i++){
        mp[z[i]] = i;
        sum[i] = (sum[i - 1] + dp[i - 1])%mod;
        dp[i] = inv*(sum[i] - sum[mp[ind[z[i]]]] + mod)%mod;
    }
    /*for(auto p:v[0]) cout << p.first.second << " " << p.first.first << endl;
    for(i=0;i<=n;i++) cout << ind[i] << " ";
    cout << endl;*/
    ll ans = 0;
    int x = -1;
    for(auto p:v[0]) x = max(x,p.first.second);
    /*for(i=0;i<=n;i++){
        cout << dp[i]*pw(2,i)%mod << " ";
    }
    cout << endl;*/
    /*for(i=0;i<z.size();i++){
        cout << dp[i] << " ";
    }
    cout << endl;
    cout << x << endl;*/
    /*for(i=0;i<z.size();i++){
        cout << dp[i]*pw(2,i)%mod << " ";
    }
    cout << endl;
    cout << x << " " << z.size() << endl;*/
    for(i=0;i<z.size() - 1;i++){
        if(z[i]>=x){
            //cout << z[i] << endl;
            (ans += dp[i]*pw(2,i + z.size() - 2 - i)%mod) %= mod;
        }
    }
    /*for(i=0;i<z.size() - 1;i++){
        //cout << dp[i]*pw(2,i)%mod << " ";
        if(ind[n + 1]<=z[i]) (ans += dp[i]*pw(2,i + z.size() - 2 - i)%mod) %= mod;
    }*/
    //cout << endl;
    //cout << ans << " c " << endl;
    /*for(int x:z) cout << x << " ";
    cout << endl;*/
    init(2*n + 1);
    for(auto p:v[1]){
        int l = p.first.first - 1,r = p.first.second;
        l = nz[upper_bound(nz.begin(),nz.end(),l) - nz.begin() - 1];
        if(p.second==1){
            if(l>1) unite(2*l - 1,2*r - 1),unite(2*l,2*r);
            else unite(0,2*r - 1);
        }
        if(p.second==-1){
            if(l>1) unite(2*l - 1,2*r),unite(2*l,2*r - 1);
            else unite(0,2*r);
        }
    }
    ll ans1 = 1;
    for(int x:nz){
        if(x==0 || find(2*x - 1)!=2*x - 1) continue;
        if(same(2*x - 1,2*x)){
            cout << 0 << endl;
            return 0;
        }
        if(same(0,2*x - 1) || same(0,2*x)) continue;
        (ans1 *= 2) %= mod;
    }
    //cout << ans << " " << ans1 << endl;
    cout << ans*ans1%mod << endl;
}
0