Submission #990863

#	Time	Username	Problem	Language	Result	Execution time	Memory
990863		prvocislo	Port Facility (JOI17_port_facility)	C++17	78 / 100	6058 ms	765188 KiB

port_facility

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

const int mod = 1e9 + 7;
int mul(int a, int b) { return (a * 1ll * b) % mod; }
struct bod
{
    int x, y, i;
};
vector<bod> a;
vector<int> col;
struct segment_tree2d
{
    int n2 = 1; bool sw = false;
    vector<vector<int> > st;
    vector<int> l, r;
    void initialize(int n, bool swap)
    {
        sw = swap;
        while (n2 <= 2 * n) n2 <<= 1;
        st.assign(n2 * 2, {}), l.assign(n2 * 2, -1), r.assign(n2 * 2, -1);
        for (int i = n2; i < n2 * 2; i++) l[i] = r[i] = i - n2;
        for (int i = n2 - 1; i > 0; i--) l[i] = l[i * 2], r[i] = r[i * 2 + 1];
    }
    void add(int x, int i, int vr = 1)
    {
        if (x < l[vr] || x > r[vr]) return;
        st[vr].push_back(i);
        if (x == l[vr] && r[vr] == x) return;
        add(x, i, vr * 2), add(x, i, vr * 2 + 1);
    }
    void query(int x1, int x2, int y1, int y2, int c, set<pair<int, int> >& q, int vr = 1)
    {
        if (x2 < l[vr] || r[vr] < x1) return;
        if (x1 <= l[vr] && r[vr] <= x2)
        {
            while (!st[vr].empty() &&
                ((!sw && x1 <= a[st[vr].back()].x && a[st[vr].back()].x <= x2 && y1 <= a[st[vr].back()].y && a[st[vr].back()].y <= y2) ||
                    (sw && y1 <= a[st[vr].back()].x && a[st[vr].back()].x <= y2 && x1 <= a[st[vr].back()].y && a[st[vr].back()].y <= x2)))
            {
                if (col[a[st[vr].back()].i] == -1)
                {
                    q.insert({ a[st[vr].back()].x, st[vr].back() });
                    col[a[st[vr].back()].i] = c;
                }
                st[vr].pop_back();
            }
            return;
        }
        query(x1, x2, y1, y2, c, q, vr * 2);
        query(x1, x2, y1, y2, c, q, vr * 2 + 1);
    }
};
bool cmpxs(bod a, bod b) { return a.y < b.y; }
bool cmpys(bod a, bod b) { return a.x > b.x; }
bool cmpi(bod a, bod b) { return a.i < b.i; }
segment_tree2d xs, ys;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    xs.initialize(n, false), ys.initialize(n, true);
    a.resize(n), col.resize(n, -1);
    vector<int> id(2 * n);
    for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y, a[i].i = i, id[--a[i].x] = id[--a[i].y] = i;
    sort(a.begin(), a.end(), cmpxs);
    for (bod i : a) xs.add(i.x, i.i);
    sort(a.begin(), a.end(), cmpys);
    for (bod i : a) ys.add(i.y, i.i);
    sort(a.begin(), a.end(), cmpi);
    set<pair<int, int> > ns, qu;
    for (int i = 0; i < n; i++) ns.insert({ a[i].x, a[i].i });
    int ans = 1, c = 0;
    while (!ns.empty())
    {
        int i = ns.begin()->second;
        qu.insert({ a[i].x, i }); col[i] = c;
        while (!qu.empty())
        {
            int j = qu.begin()->second;
            ns.erase(*qu.begin()), qu.erase(qu.begin());
            xs.query(a[j].x, a[j].y, a[j].y, 2 * n, col[j] ^ 1, qu);
            ys.query(a[j].x, a[j].y, 0, a[j].x, col[j] ^ 1, qu);
        }
        ans = mul(ans, 2), c += 2;
    }
    vector<vector<int> > v(c * 2);
    for (int i = 0; i < 2 * n; i++)
    {
        if (!v[col[id[i]]].empty() && v[col[id[i]]].back() == id[i]) v[col[id[i]]].pop_back();
        else v[col[id[i]]].push_back(id[i]);
    }
    for (int i = 0; i < c * 2; i++) if (!v[i].empty())
    {
        cout << "0\n";
        return 0;
    }
    cout << ans << "\n";
    return 0;
}

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