Submission #1207912

#TimeUsernameProblemLanguageResultExecution timeMemory
1207912mychecksedadPort Facility (JOI17_port_facility)C++20
22 / 100
6091 ms43060 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int n; array<int, 2> a[N]; vi g[N]; bitset<N> vis; vector<bool> col(N); void dfs(int v){ vis[v] = 1; for(int u: g[v]){ if(!vis[u]){ col[u] = !col[v]; dfs(u); }else{ if(col[u] == col[v]){ cout << 0; exit(0); } } } } void solve(){ cin >> n; for(int i = 1; i <= n; ++i){ cin >> a[i][0] >> a[i][1]; } sort(a+1, a+1+n); for(int i = 1; i <= n; ++i){ for(int j = i + 1; j <= n; ++j){ if(a[j][1] > a[i][1] && a[j][0] < a[i][1]){ g[i].pb(j); g[j].pb(i); } } } vis = 0; ll ans = 1; for(int i = 1; i <= n; ++i){ if(!vis[i]){ ans *= 2; ans %= MOD; dfs(i); } } cout << ans; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; 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...