Submission #482468

#	Time	Username	Problem	Language	Result	Execution time	Memory
482468		hidden1	Port Facility (JOI17_port_facility)	C++14	100 / 100	2432 ms	281052 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(int i = 0; i < n; i ++)
#define revn(i, n) for(int i = n - 1; i >= 0; i --)
typedef long long ll;
template<class T, template<class T2, class A=allocator<T2> > class cont> inline ostream &operator <<(ostream &out, const cont<T> &x) { for(const auto &it : x) { out << it << " ";} return out;}
template<class T, template<class T2, class A=allocator<T2> > class cont> inline istream &operator >>(istream &in, cont<T> &x) { for(auto &it : x) { in >> it;} return in;}
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
 
const int MAX_N = 1e6 + 10;
int par[MAX_N];
int dist[MAX_N];
int n;
int a[MAX_N], b[MAX_N];
int who[2 * MAX_N];
 
struct Comp {
    set<pair<int, int> > color[2];
    vector<int> all;
    int size() {
        return all.size();
    }
} comp[MAX_N];
 
void init() {
    for(int i = 0; i < MAX_N; i ++) {
        comp[i].color[0].insert({b[i], i});
        comp[i].all.push_back(i);
        par[i] = i;
        dist[i] = 0;
    }
}
 
int find(int x) {
    if(x == par[x]) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}
 
set<pair<int, int> > active;
 
void removeAll(int x) {
    x = find(x);
 
    forn(col, 2) {
        if(comp[x].color[col].empty()) {continue;}
 
        auto el = *(comp[x].color[col].begin());
        active.erase(el);
    }
}
 
void addAll(int x) {
    x = find(x);
 
    forn(col, 2) {
        if(comp[x].color[col].empty()) {continue;}
 
        auto el = *(comp[x].color[col].begin());
        active.insert(el);
    }    
}
 
vector<pair<int, int> > merged;
 
void merge(int x, int y) {
    int xx = x, yy = y;
    merged.push_back({x, y});
    x = find(x); y = find(y);
    if(x == y) {
        if(dist[xx] == dist[yy]) {
            cout << 0 << endl;
            exit(0);
        } else {
            return;
        }
    }
    if(comp[x].size() < comp[y].size()) {
        swap(x, y);
        swap(xx, yy);
    }
 
    removeAll(x);
    removeAll(y);
 
    int xr = dist[xx] ^ dist[yy] ^ 1;
 
    forn(col, 2) {
        for(auto it : comp[y].color[col]) {
            comp[x].color[col ^ xr].insert(it);
        }
 
        comp[y].color[col].clear();
    }

    for(auto it : comp[y].all) {
        dist[it] ^= xr;
        par[it] = x;
        comp[x].all.push_back(it);
    }
 
    addAll(x);
}
 
void remove(int x) {
    int p = find(x);
 
    removeAll(p);
 
    comp[p].color[dist[x]].erase({b[x], x});
 
    addAll(p);
}
 
void add(int x) {
 
    vector<int> toMerge = {};
    for(auto it : active) {
        if(it.first >= b[x]) {
            break;
        } else {
            toMerge.push_back(it.second);
        }
    }
 
    if(toMerge.empty()) {
        addAll(x);
    } else {
        for(auto it : toMerge) {
            merge(x, it);
        }
    }
}
  
signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> a[i] >> b[i];
        a[i] --;
        b[i] --;
        who[a[i]] = i;
        who[b[i]] = -i;
    }
  
    init();


    for(int i = 0; i < 2 * n; i ++) {
        if(who[i] < 0) {
            remove(-who[i]);
        } else {
            add(who[i]);
        }
    }
 
    ll pw = 1;
 
    for(int i = 1; i <= n; i ++) {
        if(par[i] == i) {
            pw = (pw * 2ll) % mod;
        }
    }
 
    cout << pw << endl;
 
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22