結果

問題 No.1222 -101
コンテスト
ユーザー pockyny
提出日時 2020-09-07 21:39:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 350 ms / 2,000 ms
コード長 4,014 bytes
コンパイル時間 1,495 ms
コンパイル使用メモリ 98,468 KB
最終ジャッジ日時 2025-01-14 08:15:55
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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