Submission #359424

#	Time	Username	Problem	Language	Result	Execution time	Memory
359424		ijxjdjd	Port Facility (JOI17_port_facility)	C++14	100 / 100	791 ms	163644 KiB

port_facility

#include <bits/stdc++.h>
#include <assert.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;

const int MAXN = (int)(5e5) + 5;
int erase(pair<set<int>, set<int>>& s, int val, bool rem) {
    if (s.first.find(val) != s.first.end()) {
        if (rem) {
            s.first.erase(s.first.find(val));
        }
        return 0;
    }
    else {
        if (rem) {
            s.second.erase(s.second.find(val));
        }
        return 1;
    }
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N;
	cin >> N;
	vector<int> order;
	order.resize(2*N);
	FR(i, N) {
	    int a, b;
	    cin >> a >> b;
	    a--, b--;
	    order[a] = b;
	    order[b] = -a;
	}
	bool zero = false;
	int cnt = 0;
	vector<pair<set<int>, set<int>>> intervals;
	for (int i = 0; i < 2*N; i++) {
        if (order[i] <= 0) {
            erase(intervals.back(), i, true);
            if (intervals.back().first.size() + intervals.back().second.size()  == 0) {
                intervals.pop_back();
                cnt++;
            }
        }
        else {
            if (intervals.size() == 0) {
                intervals.emplace_back();
                intervals.back().first.insert(order[i]);
            }
            else {
                int j = intervals.size()-1;
                pair<set<int>, set<int>> add;
                add.first.insert(order[i]);
                intervals.push_back(add);
                while (j >= 0) {
                    auto& next = intervals.back();
                    if (intervals[j].first.size() == 0) {
                        swap(intervals[j].first, intervals[j].second);
                    }
                    if (intervals[j].second.size() == 0) {
                        if (*intervals[j].first.begin() <= order[i]) {
                            int col = erase(next, order[i], false);
                            if (intervals[j].first.size() + intervals[j].second.size() > next.first.size() + next.second.size()) {
                                swap(intervals[j], next);
                            }
                            if (col == 0) {
                                swap(intervals[j].first, intervals[j].second);
                            }
                            next.first.insert(intervals[j].first.begin(), intervals[j].first.end());
                            next.second.insert(intervals[j].second.begin(), intervals[j].second.end());
                        }
                        else {
                            break;
                        }

                    }
                    else {
                        if (max(*intervals[j].first.begin(), *intervals[j].second.begin()) <= order[i]) {
                            zero = true;
                            i = 3*N;
                            break;
                        }
                        else if (min(*intervals[j].first.begin(), *intervals[j].second.begin()) >= order[i]){
                            break;
                        }
                        else {
                            int col = erase(next, order[i], false);
                            if (*intervals[j].first.begin() > *intervals[j].second.begin()) {
                                swap(intervals[j].first, intervals[j].second);
                            }
                            if (next.first.size() + next.second.size() < intervals[j].first.size() + intervals[j].second.size()) {
                                swap(next, intervals[j]);
                            }
                            if (col == 0) {
                                swap(intervals[j].first, intervals[j].second);
                            }
                            next.first.insert(intervals[j].first.begin(), intervals[j].first.end());
                            next.second.insert(intervals[j].second.begin(), intervals[j].second.end());

                        }
                    }
                    if (intervals.back().first.size() + intervals.back().second.size() > intervals[j].first.size() + intervals[j].second.size()) {
                        swap(intervals[j+1], intervals[j]);
                    }
                    intervals.pop_back();
                    j--;
                }
//                cout << track << '\n';
            }
        }
	}
	ll tot = !zero;
	ll MOD = (int)(1e9) + 7;
	FR(i, cnt) {
        tot += tot;
        if (tot >= MOD) {
            tot -= MOD;
        }
    }
    cout << tot << '\n';
	return 0;
}

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