Submission #594957

#	Time	Username	Problem	Language	Result	Execution time	Memory
594957		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) {
        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 << s << ' ' << e << ' ' << 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];
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];
    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);
            //cout << i << ' ' << pt << '\n';
            tree.add2(A[pt]+1,B[pt],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);
            }
            else {
                tree.add2(A[pt],B[pt],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> S2;
    for(i=0;i<2*N;i++) {
        S2.insert(UF.Find(i));
    }
    //cout << "chk\n";
    cout << power(2, S2.size(), p);
}

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:83:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |         int mid = ns + ne >> 1;
      |                   ~~~^~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:117:12: warning: unused variable 'j' [-Wunused-variable]
  117 |     int i, j;
      |            ^

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