Submission #482074

#	Time	Username	Problem	Language	Result	Execution time	Memory
482074		hidden1	Port Facility (JOI17_port_facility)	C++14	0 / 100	77 ms	86420 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 {
    vector<int> color[2];
    int size() {
        return color[0].size() + color[1].size();
    }
} comp[MAX_N];

void init() {
    for(int i = 0; i < MAX_N; i ++) {
        comp[i].color[0].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].back();
        auto it = active.find({b[el], el});
        if(it != active.end()) {
            cerr << "erasing " << *it << endl;
            active.erase(it);
        }
    }
}

void addAll(int x) {
    x = find(x);

    forn(col, 2) {
        if(comp[x].color[col].empty()) {continue;}

        auto el = comp[x].color[col].back();
        active.insert({b[el], el});
    }    
}

vector<pair<int, int> > merged;

void printComp();

void merge(int x, int y) {
    cerr << "Merging " << x << " " << y << " " << dist[x] << " " << dist[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]) {
            cerr << endl;
            for(auto it : merged) {
                cerr << it << "  " << a[it.first] << " " << b[it.first] << "  " << a[it.second] << " " << b[it.second] << endl;
            }
            cerr << 0 << endl;
            exit(0);
        } else {
            return;
        }
    }
    if(comp[x].size() < comp[y].size()) {
        swap(x, y);
    }

    removeAll(x);
    removeAll(y);

    int xr = dist[xx] ^ 1;

    forn(col, 2) {
        for(auto it : comp[y].color[col]) {
            comp[x].color[col ^ xr].push_back(it);
            dist[it] ^= xr;
            par[it] = x;
        }

        comp[y].color[col].resize(0);
        sort(all(comp[x].color[col ^ xr]), [](const int x, const int y) { return b[x] > b[y]; });
    }

    addAll(x);

    printComp();
}

void remove(int x) {
    cerr << "Removing " << x << endl;

    int p = find(x);

    removeAll(p);

    cerr << "removing from " << p << " " << dist[x] << endl;

    comp[p].color[dist[x]].pop_back();

    addAll(p);
}

void add(int x) {
    cerr << "Adding " << x << endl;

    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);
        }
    }
}

void printComp() {
    cerr << "~~~~~~~~" << endl;;
    for(int i = 1; i <= n; i ++) {
        cerr << "Comp " << i << endl;
        if(par[i] != i) {continue;}
        forn(col, 2) {
            cerr << "For col " << col << ": ";
            for(auto it : comp[i].color[col]) {
                cerr << "{" << it << "|" << b[it] << "}" << ", ";
            }
            cerr << endl;
        }
    }
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    init();

    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;
    }

    for(int i = 0; i < 2 * n; i ++) {
        if(who[i] < 0) {
            remove(-who[i]);
        } else {
            add(who[i]);
        }
        
        printComp();
        cerr << "Active is : ";
        for(auto it : active) {
            cerr << it << " | ";
        }
        cerr << endl;
        cerr << endl;
        for(int j = 1; j <= n; j ++) {
            cerr << par[j] << " ";
        }
        cerr << endl;
        for(int j = 1; j <= n; j ++) {
            cerr << dist[j] << " ";
        }
        cerr << endl;
        cerr << "|||||||||||||||" << endl;
    }

    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: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22