제출 #1294118

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1294118		thnhann	Port Facility (JOI17_port_facility)	C++20	100 / 100	2507 ms	383932 KiB

port_facility

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx,avx2,fma,lzcnt,popcnt")
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define ii pair<int,int>
#define ill pair<ll,ll>
#define el cout<<'\n'
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

const ll mod=1e9+7;
const int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
const int nmax=2e6;
const int inf =2e9;

void add(int &a, int b) {
    a += b;
    if (a >= mod) a -= mod;
    if (a < 0) a += mod;
}

void sub ( int&a , int b ) { if ((a-=b) < 0 ) a += mod ; }

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r)
{
    return uniform_int_distribution<int>(l, r) (rd);
}

int n;
ii range[nmax + 5];
int col[nmax + 5];

struct Tree{
    vector<pair<int,int>>t;
    Tree(){}
    void init(int sz)
    {
        t.resize(4 * sz + 5,{-inf,0});
    }
    void update(int id,int l,int r,int pos,ii val)
    {
        if(l > pos || r < pos)
            return;
        if(l == r)
        {
            t[id] = val;
            return;
        }
        int mid = (l + r) >> 1;
        update(id<<1,l,mid,pos,val);
        update(id<<1 | 1,mid+1,r,pos,val);
        t[id] = max(t[id << 1],t[id << 1 | 1]);
    }
    ii get(int id,int l,int r,int u,int v)
    {
        if(l > v || r < u)
        {
            return(make_pair(-inf,0));
        }
        if(u <= l && r <= v)
            return t[id];
        int mid = (l + r) >> 1;
        return max(get(id<<1,l,mid,u,v),get(id<<1 | 1,mid+1,r,u,v));
    }
}treemax,treemin;

void dfs(int u,int color){
    col[u] = color;
    treemax.update(1,1,2*n,range[u].fi,{-inf,0});
    treemin.update(1,1,2*n,range[u].se,{-inf,0});
    while(true)
    {
        int v = treemax.get(1,1,2*n,range[u].fi,range[u].se - 1).se;
        if(!v || range[v].se <= range[u].se) break;
        dfs(v,3 - color);
    }
    while(true)
    {
        int v = treemin.get(1,1,2*n,range[u].fi,range[u].se - 1).se;
        if(!v || range[v].fi > range[u].fi) break;
        dfs(v,3 - color);
    }
}

int st[nmax + 5];
int event[nmax + 5];

bool check(int type)
{
    for(int i=1;i<=2*n;i++)
        event[i] = 0;
    for(int i=1;i<=n;i++)
        if(col[i] == type)
    {
        event[range[i].fi] = i;
        event[range[i].se] = i;
    }
    int top = 0;
    for(int i=1;i<=2*n;i++)
    {
        if(event[i])
        {
            if(top > 0 && st[top] == event[i])
                top--;
            else
            {
                st[++top] = event[i];
            }
        }
    }
    return (top == 0);
}

signed main()
{
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   cin >> n;
   for(int i=1;i<=n;i++)
    cin >> range[i].fi >> range[i].se;
   treemax.init(2*n);
   treemin.init(2*n);
   for(int i=1;i<=n;i++)
   {
       treemax.update(1,1,2*n,range[i].fi,{range[i].se,i});
       treemin.update(1,1,2*n,range[i].se,{-range[i].fi,i});
   }
   int ans  = 1;
   for(int i=1;i<=n;i++)
    if(!col[i])
   {
       dfs(i,1);
       ans = (ans * 2)%mod;
   }
   if(!check(1) || !check(2)){
    cout << 0;
    return 0;
   }
   cout << ans;

}
//  "Can i get a kiss? And can u make it last forever?"

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