제출 #1341572

#제출 시각아이디문제언어결과실행 시간메모리
1341572nguyenkhangninh99Port Facility (JOI17_port_facility)C++20
100 / 100
2827 ms534480 KiB
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1e6 + 5, mod = 1e9 + 7;
vector<int> g[maxn], at[8 * maxn];
int vis[maxn];


void update(int id, int l, int r, int p, int val){
	at[id].push_back(val);
	if(l == r) return;
    int mid = (l + r) / 2;
    if(p <= mid) update(id * 2, l, mid, p, val);
    else update(id * 2 + 1, mid + 1, r, p, val);
}

void query(int id, int l, int r, int u, int v, int val){
	if(v < l || r < u) return;
	if(u <= l && r <= v){
        for(int x: at[id]){
			g[val].push_back(x);
			g[x].push_back(val);
        }
		if(at[id].size()) at[id] = {at[id][0]};
		return;
	}
    int mid = (l + r) / 2;
	query(id * 2, l, mid, u, v, val);
	query(id * 2 + 1, mid + 1, r, u, v, val);
}

bool dfs(int u){
    bool res = true;
    for(int v: g[u]){
        if(!vis[v]){
            vis[v] = vis[u] ^ 3;
            res &= dfs(v);
        }else if(vis[v] == vis[u]) return false;
    }
    return res;
}
int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

	int n; cin >> n;
    vector<array<int, 2>> a(n + 1);
	
    for(int i = 1; i <= n; i++) cin >> a[i][0] >> a[i][1];
	sort(a.begin() + 1, a.end());

	for(int i = 1; i <= n; i++){
	    query(1, 1, 2 * n, a[i][0], a[i][1], i);
        update(1, 1, 2 * n, a[i][1], i);
	}
	int ans = 1;
	for(int i = 1; i <= n; i++){
		if(vis[i]) continue;
		(ans *= 2) %= mod;
        
		vis[i] = 1;
        if(!dfs(i)) ans = 0;
	}
	cout << ans;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...