Submission #1192174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192174		dragst	Port Facility (JOI17_port_facility)	C++20	78 / 100	3642 ms	1088136 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

const long long mod=1e9+7;
long long check, p[1000005], r[1000005], a[1000005], b[1000005], id[1000005], id2[8000005], sz[8000005], pos[2000005], check2[1000005];
vector<long long> st[8000005], adj[1000005];

bool sortt(long long x, long long y) {return a[x]<a[y];}

void makeset(long long x)
{
    p[x]=x;
    r[x]=0;
}

long long findset(long long x)
{
    if (p[x]!=x) {p[x]=findset(p[x]);};
    return p[x];
}

void unionsets(long long x, long long y)
{
    x=findset(x);
    y=findset(y);
    if (x!=y)
    {
        if (r[x]<r[y]) {swap(x, y);};
        p[y]=x;
        if (r[x]==r[y]) {r[x]++;};
    };
}

void build(long long x, long long l, long long r)
{
    if (l>r) {return;}
    else if (l==r)
    {
        if (pos[l]) {st[x].push_back(pos[l]);};
        id2[x]=0; sz[x]=st[x].size();
    }
    else
    {
        build(x*2, l, (l+r)/2);
        build(x*2+1, (l+r)/2+1, r);
        long long i=0, j=0, sz1=st[x*2].size(), sz2=st[x*2+1].size();
        while (i<sz1 || j<sz2)
        {
            if (i==sz1) {st[x].push_back(st[x*2+1][j]); j++;}
            else if (j==sz2) {st[x].push_back(st[x*2][i]); i++;}
            else if (a[st[x*2][i]]<a[st[x*2+1][j]]) {st[x].push_back(st[x*2][i]); i++;}
            else {st[x].push_back(st[x*2+1][j]); j++;};
        };
        id2[x]=0; sz[x]=st[x].size();
    };
}

void update(long long x, long long l, long long r, long long pos1, long long pos2)
{
    if (l>r || l>pos2 || r<pos1 || pos1>pos2) {return;}
    else if (pos1<=l && r<=pos2)
    {
        if (!st[x].empty() && a[st[x][0]]<pos1) {adj[pos[pos2+1]].push_back(st[x][0]); adj[st[x][0]].push_back(pos[pos2+1]);};
        while (id2[x]<sz[x] && a[st[x][id2[x]]]<pos1)
        {
            if (id2[x]>0) {unionsets(st[x][id2[x]-1], st[x][id2[x]]);};
            id2[x]++;
        };
    }
    else
    {
        update(x*2, l, (l+r)/2, pos1, pos2);
        update(x*2+1, (l+r)/2+1, r, pos1, pos2);
    };
}

void dfs(long long x, long long col)
{
    check2[x]=col+1;
    for (auto y: adj[x])
    {
        y=findset(y);
        if (check2[y]==0) {dfs(y, 1-col);}
        else if (check2[y]==check2[x]) {check=0;};
    };
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, i, ans=1;
    cin >> n;
    for (i=1; i<=n; i++)
    {
        cin >> a[i] >> b[i];
        id[i]=pos[b[i]]=i;
        makeset(i);
    };
    sort(id+1, id+n+1, sortt);
    build(1, 1, 2*n);
    for (i=1; i<=n; i++)
    {
        update(1, 1, 2*n, a[id[i]]+1, b[id[i]]-1);
    };
    check=1;
    for (i=1; i<=n; i++)
    {
        if (findset(i)!=i) {for (auto x: adj[i]) {adj[findset(i)].push_back(x);};};
    };
    for (i=1; i<=n; i++)
    {
        if (check2[findset(i)]==0) {dfs(findset(i), 0);};
    };
    if (check==0) {cout << 0;}
    else
    {
        for (i=1; i<=n; i++)
        {
            for (auto x: adj[i]) {unionsets(i, x);};
        };
        for (i=1; i<=n; i++)
        {
            if (findset(i)==i) {ans*=2; ans%=mod;};
        };
        cout << ans;
    };
}

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