제출 #990868

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
990868		prvocislo	Port Facility (JOI17_port_facility)	C++17	100 / 100	5344 ms	765104 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> in;
vector<int> col;
struct segment_tree2d
{
    int n2 = 1; bool sw = false;
    vector<vector<int> > st;
    vector<int> l, r;
    void run(const vector<int>& b, int vr = 1)
    {
        for (int i : b) if ((!sw && l[vr] <= a[i].x && a[i].x <= r[vr]) || (sw && l[vr] <= a[i].y && a[i].y <= r[vr])) st[vr].push_back(i);
        if (vr < n2) run(st[vr], vr * 2), run(st[vr], vr * 2 + 1);
    }
    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];
        run(in);
    }
    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(int i, int j) { return a[i].y < a[j].y; }
bool cmpys(int i, int j) { return a[i].x > a[j].x; }
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, in.push_back(i);
    sort(in.begin(), in.end(), cmpxs);
    xs.initialize(n, false);
    sort(in.begin(), in.end(), cmpys); 
    ys.initialize(n, true);
    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: 22 / 22