Submission #543303

#	Time	Username	Problem	Language	Result	Execution time	Memory
543303		Fysty	Port Facility (JOI17_port_facility)	C++17	100 / 100	3634 ms	442748 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
//#define int ll
#define MottoHayaku ios::sync_with_stdio(0);cin.tie(0);
#define F first
#define S second
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end());uni(c);
#define X first
#define Y second

const int MOD=1e9+7;
const int N=1e6+5;
int bid[N*2],a[N],b[N],now[N<<3];
vector<int> st[N<<3];

int par[N],c[N];
bool vis[N];

int fp(int x)
{
    if(par[x]==x) return x;
    int tmp=fp(par[x]);
    c[x]^=c[par[x]];
    return par[x]=tmp;
}
bool unite(int u,int v,int w)
{
    //cout<<u<<" "<<v<<" "<<w<<"\n";
    int x=fp(u),y=fp(v);
    if(x==y)
    {
        if(c[u]^c[v]!=w) return false;
        else return true;
    }
    c[y]=c[u]^c[v]^w;
    par[y]=x;
    return true;
}

void build(int l,int r,int id)
{
    now[id]=1;
    if(l==r)
    {
        if(bid[l]!=0) st[id]={bid[l]};
        //cout<<l<<" "<<r<<" "<<st[id].size()<<"\n";
    }
    else
    {
        int mid=l+r>>1;
        build(l,mid,id<<1);
        build(mid+1,r,id<<1|1);
        int cur=0;
        rep(i,st[id<<1].size())
        {
            while(cur<st[id<<1|1].size()&&a[st[id<<1|1][cur]]<a[st[id<<1][i]])
            {
                st[id].pb(st[id<<1|1][cur]);
                cur++;
            }
            st[id].pb(st[id<<1][i]);
        }
        while(cur<st[id<<1|1].size())
        {
            st[id].pb(st[id<<1|1][cur]);
            cur++;
        }
        //cout<<l<<" "<<r<<" "<<st[id].size()<<"\n";
    }
}
bool add(int l,int r,int ql,int qr,int i,int id)
{
    if(ql<=l&&r<=qr)
    {
        //cout<<l<<" "<<r<<" "<<ql<<" "<<qr<<" "<<i<<"\n";
        if(st[id].size()==0||a[st[id][0]]>a[i]) return true;
        bool ret=1;
        ret&=unite(i,st[id][0],1);
        //cout<<st[id].size()<<"size\n";
        while(now[id]<st[id].size()&&a[st[id][now[id]]]<a[i])
        {
            ret&=unite(st[id][now[id]],st[id][now[id]-1],0);
            now[id]++;
        }
        return ret;
    }
    else
    {
        int mid=l+r>>1;
        if(qr<=mid) return add(l,mid,ql,qr,i,id<<1);
        else if(ql>mid) return add(mid+1,r,ql,qr,i,id<<1|1);
        else return add(l,mid,ql,mid,i,id<<1)&add(mid+1,r,mid+1,qr,i,id<<1|1);
    }
}
signed main()
{
    MottoHayaku
    ll n;
    cin>>n;
    vector<pll> tmp(n);
    rep(i,n) cin>>tmp[i].F>>tmp[i].S;
    sort(tmp.begin(),tmp.end());
    rep1(i,n)
    {
        a[i]=tmp[i-1].F,b[i]=tmp[i-1].S;
        bid[b[i]]=i;
    }
    rep1(i,n) par[i]=i;
    build(1,2*n,1);
    bool can=1;
    rep1(i,n)
    {
        can&=add(1,2*n,a[i],b[i]-1,i,1);
    }
    if(!can)
    {
        cout<<0;
        return 0;
    }
    ll ans=1;
    rep1(i,n)
    {
        if(vis[fp(i)]) continue;
        vis[fp(i)]=1;
        ans=ans*2%MOD;
    }
    cout<<ans;
}

Compilation message (stderr)

port_facility.cpp: In function 'bool unite(int, int, int)':
port_facility.cpp:38:21: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   38 |         if(c[u]^c[v]!=w) return false;
      |                 ~~~~^~~
port_facility.cpp: In function 'void build(int, int, int)':
port_facility.cpp:56:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |         int mid=l+r>>1;
      |                 ~^~
port_facility.cpp:9:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define rep(i,n) for(int i=0;i<n;i++)
......
   60 |         rep(i,st[id<<1].size())
      |             ~~~~~~~~~~~~~~~~~~ 
port_facility.cpp:60:9: note: in expansion of macro 'rep'
   60 |         rep(i,st[id<<1].size())
      |         ^~~
port_facility.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             while(cur<st[id<<1|1].size()&&a[st[id<<1|1][cur]]<a[st[id<<1][i]])
      |                   ~~~^~~~~~~~~~~~~~~~~~~
port_facility.cpp:69:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |         while(cur<st[id<<1|1].size())
      |               ~~~^~~~~~~~~~~~~~~~~~~
port_facility.cpp: In function 'bool add(int, int, int, int, int, int)':
port_facility.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         while(now[id]<st[id].size()&&a[st[id][now[id]]]<a[i])
      |               ~~~~~~~^~~~~~~~~~~~~~
port_facility.cpp:95:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |         int mid=l+r>>1;
      |                 ~^~

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