제출 #1192171

#제출 시각아이디문제언어결과실행 시간메모리
1192171dragstPort Facility (JOI17_port_facility)C++20
0 / 100
179 ms376236 KiB
#include <bits/stdc++.h>
using namespace std;

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

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

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, i, check=1, 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);
    };
    for (i=1; i<=n; i++)
    {
        for (auto x: adj[i])
        {
            if (findset(i)==findset(x)) {check=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;
    };
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...