Submission #318912

#	Time	Username	Problem	Language	Result	Execution time	Memory
318912		mhy908	Port Facility (JOI17_port_facility)	C++14	78 / 100	6062 ms	247696 KiB

port_facility

#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const LL mod=1e9+7;

struct UNION_FIND{
    int par[2000010], sz;
    UNION_FIND(){for(int i=1; i<=2000000; i++)par[i]=i;}
    int findpar(int num){return num==par[num]?num:par[num]=findpar(par[num]);}
    void mergepar(int a, int b){
        a=findpar(a); b=findpar(b);
        if(a==b)return;
        par[a]=b;
        sz--;
    }
}uf;

int n;
pii arr[1000010];

int stk1[1000010][25], stk2[1000010][25];
int re1[4000010], re2[4000010];

void con1(int point, int lv, int s, int e, int a, int b, int to){
    if(e<a||s>b)return;
    if(a<=s&&e<=b){
        if(!re1[point])return;
        for(int i=1; i<=re1[point]; i++)uf.mergepar(stk1[s+i-1][lv], to);
        re1[point]=1;
        return;
    }
    con1(point*2, lv+1, s, (s+e)/2, a, b, to);
    con1(point*2+1, lv+1, (s+e)/2+1, e, a, b, to);
}
void con2(int point, int lv, int s, int e, int a, int b, int to){
    if(e<a||s>b)return;
    if(a<=s&&e<=b){
        if(!re2[point])return;
        for(int i=1; i<=re2[point]; i++)uf.mergepar(stk2[s+i-1][lv], to);
        re2[point]=1;
        return;
    }
    con2(point*2, lv+1, s, (s+e)/2, a, b, to);
    con2(point*2+1, lv+1, (s+e)/2+1, e, a, b, to);
}
void upd1(int point, int lv, int s, int e, int num, int val){
    stk1[s+re1[point]][lv]=val;
    re1[point]++;
    if(s==e)return;
    if(num<=(s+e)/2)upd1(point*2, lv+1, s, (s+e)/2, num, val);
    else upd1(point*2+1, lv+1, (s+e)/2+1, e, num, val);
}
void upd2(int point, int lv, int s, int e, int num, int val){
    stk2[s+re2[point]][lv]=val;
    re2[point]++;
    if(s==e)return;
    if(num<=(s+e)/2)upd2(point*2, lv+1, s, (s+e)/2, num, val);
    else upd2(point*2+1, lv+1, (s+e)/2+1, e, num, val);
}
inline int readChar();
template<class T=int> inline T readInt();
static const int buf_size=4096;
inline int getChar() {
    static char buf[buf_size];
    static int len=0, pos=0;
    if(pos==len)pos=0, len=fread(buf, 1, buf_size, stdin);
    if(pos==len)return -1;
    return buf[pos++];
}
inline int readChar() {
    int c=getChar();
    while(c<=32)c=getChar();
    return c;
}
template <class T>
inline T readInt() {
    int s=1, c=readChar();
    T x=0;
    if(c=='-')s=-1, c=getChar();
    while('0'<=c&&c<='9')x=x*10+c-'0', c=getChar();
    return s==1?x:-x;
}
LL ans=1;
vector<int> id;
int main(){
    //scanf("%d", &n);
    n=readInt();
    uf.sz=2*n;
    for(int i=1; i<=n; i++){
        arr[i].F=readInt();
        arr[i].S=readInt();
        id.eb(arr[i].S);
        //scanf("%d %d", &arr[i].F, &arr[i].S);
    }
    sort(id.begin(), id.end());
    id.erase(unique(id.begin(), id.end()), id.end());
    sort(arr+1, arr+n+1);
    for(int i=1; i<=n; i++){
        int e=lower_bound(id.begin(), id.end(), arr[i].S)-id.begin()+1;
        int s=upper_bound(id.begin(), id.end(), arr[i].F)-id.begin()+1;
        con1(1, 0, 1, n, s, e, i+n);
        con2(1, 0, 1, n, s, e, i);
        upd1(1, 0, 1, n, e, i);
        upd2(1, 0, 1, n, e, i+n);
    }
    for(int i=1; i<=n; i++){
        if(uf.findpar(i)==uf.findpar(i+n))return !printf("0");
    }
    for(int i=1; i<=uf.sz/2; i++)ans=ans*2%mod;
    printf("%lld", ans);
}

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