Submission #488315

#	Time	Username	Problem	Language	Result	Execution time	Memory
488315		i_am_noob	Port Facility (JOI17_port_facility)	C++17	0 / 100	124 ms	151144 KiB

port_facility

#pragma GCC target("avx2")
#include<bits/stdc++.h>
#include<x86intrin.h>
#include<immintrin.h>
//#pragma GCC optimize("unroll-loops")
using namespace std;

#define ll long long
//#define int ll
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
//#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
//#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif

inline char readchar(){
    const int maxn=1000000;
    static char buf[maxn],*p=buf,*q=buf;
    if(p==q&&(q=(p=buf)+fread(buf,1,maxn,stdin))==buf) return EOF;
    else return *p++;
}
inline int readint(){
    int c=readchar(),x=0,neg=0;
    while((c<'0'||c>'9')&&c!='-'&&c!=EOF) c=readchar();
    if(c=='-') neg=1,c=readchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=readchar();
    return neg?-x:x;
}

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=1000005;
//i_am_noob
#define v8si __attribute__ (( vector_size(32) )) signed

int val[maxn*8];

void pull(int k){val[k]=max(val[k<<1],val[k<<1|1]);}

void modify(int k, int l, int r, int p, int x){
    if(l==r){
        val[k]=x;
        return;
    }
    int mid=l+r>>1;
    if(p<=mid) modify(k<<1,l,mid,p,x);
    else modify(k<<1|1,mid+1,r,p,x);
    pull(k);
}

int query(int k, int l, int r, int ql, int qr){
    if(l>qr||r<ql) return -inf;
    if(ql<=l&&qr>=r) return val[k];
    int mid=l+r>>1;
    return max(query(k<<1,l,mid,ql,qr),query(k<<1|1,mid+1,r,ql,qr));
}

int par[maxn*2];
bool same[maxn*2];
vector<int> child[maxn*2];

int Find(int x){return par[x]==x?x:par[x]=Find(par[x]);}
void Union(int x, int y){
    bug(x,y);
    if(sz(child[Find(x)])<sz(child[Find(y)])) swap(x,y);
    int a=Find(x),b=Find(y);
    if(a==b){
        if(same[x]^same[y]){
            cout << "0\n";
            exit(0);
        }
        return;
    }
    if(!(same[a]^same[b])){
        for(auto i: child[b]) same[i]^=1;
    }
    for(auto i: child[b]) child[a].pb(i);
    child[b].clear();
    par[b]=a;
}

int n,a[maxn*2];

void orzck(){
    rep(maxn*8) val[i]=-inf;
    rep(maxn*2) par[i]=i,child[i].pb(i),same[i]=1;
    cin >> n;
    rep(n){
        int x,y;
        cin >> x >> y;
        x--,y--;
        a[x]=y,a[y]=x;
    }
    rep(2*n) if(a[i]<i){
        int x=query(1,0,2*n-1,0,a[i]-1);
        if(x<a[i]){
            modify(1,0,2*n-1,a[i],i);
            continue;
        }
        Union(a[x],a[i]);
        modify(1,0,2*n-1,a[x],-inf);
        while(1){
            int y=query(1,0,2*n-1,0,a[i]-1);
            if(y<a[i]) break;
            Union(a[y],a[i]);
            modify(1,0,2*n-1,a[y],-inf);
        }
        modify(1,0,2*n-1,a[x],x);
        modify(1,0,2*n-1,a[i],i);
    }
    set<int> st;
    rep(2*n) if(a[i]>i) st.insert(Find(i));
    int res=1;
    rep(sz(st)) res=res*2%MOD;
    cout << res << "\n";
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    #ifdef i_am_noob
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    freopen("output2.txt","w",stderr);
    #endif
    cout << fixed << setprecision(15);
    orzck();
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'void modify(int, int, int, int, int)':
port_facility.cpp:62:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int mid=l+r>>1;
      |             ~^~
port_facility.cpp: In function 'int query(int, int, int, int, int)':
port_facility.cpp:71:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int mid=l+r>>1;
      |             ~^~
port_facility.cpp: In function 'void Union(int, int)':
port_facility.cpp:30:18: warning: statement has no effect [-Wunused-value]
   30 | #define bug(...) 826
      |                  ^~~
port_facility.cpp:81:5: note: in expansion of macro 'bug'
   81 |     bug(x,y);
      |     ^~~

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