# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
550759 | AJ00 | Port Facility (JOI17_port_facility) | C++14 | 2994 ms | 1048576 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
pair<int,int> tim[1000001];
vector<int> adj[1000001];
int col[1000001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int tc=1,n,q,k,m;
//cin >> tc;
for (int poppo = 1; poppo <= tc; poppo++){
//cout << "Case #" << poppo << ": ";
cin >> n;
for (int i = 1; i <= n; i++){
cin >> tim[i].first >> tim[i].second;
col[i] = -1;
}
sort(tim+1,tim+n+1);
int cur = 1;
set<pair<int,int>> s;
// priority_queue<int, vector<int>, greater<int>> pq;
for (int i = 1; i <= (2*n); i++){
if (i != tim[cur].first){
s.erase(s.begin());
continue;
}
s.insert({tim[cur].second,cur});
for (auto const &var: s){
if (var.first == tim[cur].second){
break;
}
adj[cur].push_back(var.second);
adj[var.second].push_back(cur);
}
cur++;
}
int ans = 1;
for (int i = 1; i <= n; i++){
if (col[i] != -1){
continue;
}
col[i] = 1;
queue<int> q;
q.push(i);
while(!q.empty()){
int p = q.front();
q.pop();
for (int c: adj[p]){
if (col[c] != -1){
if (col[c] == col[p]){
cout << 0 << "\n";
return 0;
}
}
else {
col[c] = 1-col[p];
q.push(c);
}
}
}
ans = ((ans*2)%MOD);
}
cout << ans << "\n";
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |