Submission #595032

#	Time	Username	Problem	Language	Result	Execution time	Memory
595032		Cross_Ratio	Port Facility (JOI17_port_facility)	C++14	0 / 100	0 ms	340 KiB

port_facility

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> P;
const int p = 1e9 + 7;
struct UnionFind {
    vector<int> root;
    void init(int N2) {
        root.resize(N2);
        fill(root.begin(),root.end(),-1);
    }
    int Find(int n) {
        if(root[n]<0) return n;
        int r = Find(root[n]);
        root[n] = r;
        return r;
    }
    void Merge(int x, int y) {
        //cout << "Merging " << x << ' ' << y << '\n';
        x = Find(x);
        y = Find(y);
        if(x==y) return;
        if(root[x]>root[y]) swap(x, y);
        root[x] += root[y];
        root[y] = x;
    }
};
int N;
UnionFind UF;
struct SegTree {
    struct Node {
        int num;
        int p;
        Node(int n1, int p1) : num(n1), p(p1) {}
        Node() : num(-1), p(-1) {}
    };
    vector<Node> seg;
    int MAX;
    SegTree(int N2) {
        int i;
        for(i=1;i<2*N2;i*=2) {}
        seg.resize(i);
        MAX = i;
        for(i=0;i<MAX;i++) {
            seg[i].num = 3*N;
            seg[i].p = -1;
        }
    }
    void prop(int n, int ns, int ne) {
        if(seg[n].p==-1) return;
        seg[n].num = seg[n].p;
        if(n<MAX/2) {
            seg[2*n].p = seg[n].p;
            seg[2*n+1].p = seg[n].p;
        }
        seg[n].p = -1;
    }
    void add(int s, int e, int id, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e&&seg[n].num!=-1) {
            //cout << ns << ' ' << ne << ' ' << id <<' ' << seg[n].num << '\n';
            if(seg[n].num < 2*N) {
                //cout << "merge start\n";
                UF.Merge(id, seg[n].num);
                //cout << "merge done\n";
                UF.Merge((id+N)%(2*N),(seg[n].num+N)%(2*N));
                //cout << "merge done\n";
            }
            return;
        }
        int mid = (ns + ne) / 2;
        add(s,e,id,2*n, ns, mid);
        add(s,e,id,2*n+1,mid,ne);
    }
    void add2(int s, int e, int k, int n, int ns, int ne) {
        prop(n,ns,ne);
        if(e<=ns||ne<=s) return;
        if(s<=ns&&ne<=e) {
            seg[n].p = k;
            prop(n,ns,ne);
            return;
        }
        int mid = ns + ne >> 1;
        add2(s,e,k,2*n,ns,mid);
        add2(s,e,k,2*n+1,mid,ne);
        if(seg[2*n].num!=-1&&seg[2*n].num==seg[2*n+1].num) {
            seg[n].num = seg[2*n].num;
        }
        else if(seg[2*n].num==3*N) {
            seg[n].num = seg[2*n+1].num;
        }
        else if(seg[2*n+1].num==3*N) {
            seg[n].num = seg[2*n].num;
        }
        else seg[n].num = -1;
    }
};
int power(int a, int b, int c) {
    if(b==0) return 1;
    if(b==1) return a;
    if(b%2==0) {
        int k = power(a, b/2, c);
        return k * k % c;
    }
    else {
        return power(a, b-1, c) * a % c;
    }
}
int A[1000005];
int B[1000005];
int C[2000005];
int naive();
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    int i, j;
    UF.init(2*N);
    for(i=0;i<N;i++) cin >>A[i] >> B[i];
    /*vector<int> V;
    srand(6974);
    for(i=1;i<=2*N;i++) V.push_back(i);
    random_shuffle(V.begin(),V.end());
    for(i=0;i<N;i++) {
        int x = V[2*i];
        int y = V[2*i+1];
        A[i] = min(x, y);
        B[i] = max(x, y);
        cout << A[i] << ' ' << B[i] << '\n';
    }*/
    //for(i=0;i<N;i++) cin >> A[i] >> B[i];
    for(i=0;i<N;i++) A[i]--;
    for(i=0;i<N;i++) B[i]--;
    //cout << "chk\n";
    for(i=0;i<N;i++) {
        C[A[i]] = i;
        C[B[i]] = -i-1;
    }
    set<int> S;
    //cout << "chk\n";
    SegTree tree(2*N);
    //cout << "chk\n";
    int MAX = tree.MAX;
    for(i=0;i<2*N;i++) {
        int pt = (C[i]>=0?C[i]:-1-C[i]);
        //cout << i << ' ' << pt << '\n';
        if(C[i]>=0) {
            S.insert(i);
            tree.add2(i,i+1,pt,1,0,MAX/2);
        }
        else {
            tree.add(A[pt]+1,B[pt],pt+N,1,0,MAX/2);
            //tree.add2(A[pt],A[pt]+1,3*N,1,0,MAX/2);
            //cout << i << ' ' << pt << '\n';
            tree.add2(A[pt]+1,*S.rbegin()+1,pt+N,1,0,MAX/2);
            S.erase(A[pt]);
            auto it = S.lower_bound(A[pt]);
            if(it != S.end()) {
                tree.add2(A[pt],*it,3*N,1,0,MAX/2);
                //cout << A[pt] << ' ' << *it << '\n';
            }
            else {
                tree.add2(A[pt],B[pt],3*N,1,0,MAX/2);
                //cout << A[pt] << ' ' << B[pt] << '\n';
            }

        }
    }

    SegTree tree2(2*N);
    set<int> S2;
    for(i=2*N-1;i>=0;i--) {
        int pt = (C[i]>=0?C[i]:-1-C[i]);
        //cout << i << ' ' << pt << '\n';
        if(C[i]<0) {
            S2.insert(i);
            tree2.add2(i,i+1,pt,1,0,MAX/2);
        }
        else {
            tree2.add(A[pt]+1,B[pt],pt+N,1,0,MAX/2);
            //cout << i << ' ' << pt << '\n';
            tree2.add2(B[pt],B[pt]+1,3*N,1,0,MAX/2);
            //tree2.add2(*S2.begin(),B[pt],pt+N,1,0,MAX/2);
            //S2.erase(B[pt]);
            if(S2.empty()) {
                //tree2.add2(A[pt],B[pt]+1,3*N,1,0,MAX/2);
                continue;
            }
            auto it = S2.lower_bound(B[pt]);
            if(it==S2.begin()) {
                //tree2.add2(A[pt],B[pt]+1,3*N,1,0,MAX/2);
            }
            else {
                it--;
                //tree2.add2(*it,B[pt]+1,3*N,1,0,MAX/2);
            }

        }
    }
    //cout << "chk\n";
    for(i=0;i<N;i++) {
        if(UF.Find(i)==UF.Find(i+N)) {
            cout << 0;
            return 0;
        }
    }
    for(i=0;i<N;i++) {
        UF.Merge(i, i+N);
    }
    //cout << "chk\n";
    set<int> S3;
    for(i=0;i<2*N;i++) {
        S3.insert(UF.Find(i));
    }
    //cout << "chk\n";
    cout << power(2, S3.size(), p);
    //cout << '\n';
    //cout << naive();
}
vector<vector<int>> adj;
int dis[1000005];
bool isPos = true;
void dfs(int c, int pt) {
    dis[c] = pt;
    for(int n : adj[c]) {
        if(dis[n]==-1) dfs(n, pt+1);
        else {
            if(abs(dis[n]-dis[c])%2==0) isPos = false;
        }
    }
}
int naive() {
    int i, j;
    adj.resize(N);
    for(i=0;i<N;i++) dis[i] = -1;
    for(i=0;i<N;i++) {
        for(j=i+1;j<N;j++) {
            if(A[i]<A[j]&&B[i]<B[j]&&A[j]<B[i]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
            if(A[i]>A[j]&&B[i]>B[j]&&B[j]>A[i]) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    int cnt = 0;
    for(i=0;i<N;i++) {
        if(dis[i]==-1) {
            dfs(i, 0);
            cnt++;
        }
    }
    return (isPos ? power(2, cnt, p) : 0);
}

Compilation message (stderr)

port_facility.cpp: In member function 'void SegTree::add2(long long int, long long int, long long int, long long int, long long int, long long int)':
port_facility.cpp:84:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:119:12: warning: unused variable 'j' [-Wunused-variable]
  119 |     int i, j;
      |            ^

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