| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 57669 | spencercompton | Port Facility (JOI17_port_facility) | C++17 | 0 ms | 0 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;
typedef long long ll;
vector<int> comp[1000000];
vector<int> sz;
vector<int> id;
vector<bool> red;
class Ed{
public:
int id, s, e;
Ed(int a, int b, int c){
id = a;
s = b;
e = c;
}
bool operator<(const Ed &o) const{
return s<o.s;
}
};
vector<Ed> li;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
ll mod = 1000000007LL;
int n;
cin >> n;
int st[n];
int en[n];
for(int i = 0; i<n; i++){
red.push_back(true);
id.push_back(i);
sz.push_back(1);
comp[i].push_back(i);
int a, b;
cin >> a >> b;
st[i] = a;
en[i] = b;
li.push_back(Ed(i,a,b));
}
sort(li.begin(),li.end());
priority_queue<Ed> pq;
int po = n;
bool in[n];
//talking about components
bool inside[n];
//talking about elements
int last[n];
for(int i = 0; i<n; i++){
inside[i] = false;
in[i] = false;
last[i] = -1;
}
priority_queue<Ed> all[n];
for(int i = 0; i<li.size(); i++){
for(int j = 0; j<i; j++){
if(li[j].e > li[i].s && li[j].e < li[i].e){
int ca = id[li[i].id];
int cb = id[li[j].id];
if(ca==cb){
continue;
}
po--;
bool flip = red[li[i].id] == red[li[j].id];
if(sz[ca]>sz[cb]){
swap(ca,cb);
}
//ca into cb
for(int k = 0; k<comp[ca].size(); k++){
comp[cb].push_back(comp[ca][k]);
sz[cb]++;
if(flip){
red[comp[ca][k]] = !red[comp[ca][k]];
}
id[comp[ca][k]] = cb;
}
}
}
// vector<int> conflict;
// while(pq.size()>0 && -pq.top().s <li[i].s){
// int cur = pq.top().id;
// inside[cur] = false;
// pq.pop();
// while(all[id[cur]].size()>0 && -all[id[cur]].top().s<li[i].s){
// inside[all[id[cur]].top().id] = false;
// all[id[cur]].pop();
// }
// if(all[id[cur]].size()>0 && !inside[all[id[cur]].top().id]){
// Ed ee = all[id[cur]].top();
// pq.push(Ed(ee.id, ee.s,6969));
// inside[ee.id] = true;
// }
// }
// while(pq.size()>0 && -pq.top().s <li[i].e){
// int cur = pq.top().id;
// conflict.push_back(cur);
// inside[cur] = false;
// int ca = id[li[i].id];
// int cb = id[cur];
// pq.pop();
// if(ca==cb){
// continue;
// }
// po--;
// bool flip = red[li[i].id] == red[cur];
// if(sz[ca]>sz[cb]){
// swap(ca,cb);
// }
// //ca into cb
// for(int j = 0; j<comp[ca].size(); j++){
// comp[cb].push_back(comp[ca][j]);
// sz[cb]++;
// if(flip){
// red[comp[ca][j]] = !red[comp[ca][j]];
// }
// id[comp[ca][j]] = cb;
// }
// comp[ca].clear();
// while(all[ca].size()>0){
// all[ca].pop();
// }
// }
// conflict.push_back(li[i].id);
// inside[li[i].id] = false;
// vector<int> use;
// for(int j = 0; j<conflict.size(); j++){
// if(!in[id[conflict[j]]]){
// use.push_back(id[conflict[j]]);
// in[id[conflict[j]]] = true;
// }
// if(last[conflict[j]] != id[conflict[j]]){
// all[id[conflict[j]]].push(Ed(conflict[j],-en[conflict[j]],696969));
// last[conflict[j]] = id[conflict[j]];
// }
// }
// for(int j = 0; j<use.size(); j++){
// int cur = use[j];
// if(all[cur].size()>0 && !inside[all[cur].top().id]){
// inside[all[cur].top().id] = true;
// pq.push(all[cur].top());
// }
// in[cur] = false;
// }
}
ll ans = 1LL;
for(int i = 0; i<po; i++){
ans *= 2LL;
ans %= mod;
}
bool ok = true;
// priority_queue<int> reds;
// priority_queue<int> blues;
// for(int i = 0; i<n; i++){
// for(int j = i+1; j<n; j++){
// if(li[i].e > li[j].s && li[i].e < li[j].e && red[li[i].id] == red[li[j].id]){
// ok = false;
// }
// }
// }
for(int i = 0; i<li.size(); i++){
while(reds.size()>0 && -reds.top() < li[i].s){
reds.pop();
}
while(blues.size()>0 && -blues.top() < li[i].s){
blues.pop();
}
if(!red[li[i].id]){
if(blues.size()>0 && -blues.top()<li[i].e){
ok = false;
}
blues.push(-li[i].e);
}
else{
if(reds.size()>0 && -reds.top() < li[i].e){
ok = false;
}
reds.push(-li[i].e);
}
}
if(!ok){
ans = 0LL;
}
assert(ans>=0);
cout << ans << endl;
}