Submission #1131098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131098		79brue	Port Facility (JOI17_port_facility)	C++20	78 / 100	4136 ms	848312 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void no(){
    puts("0");
    exit(0);
}

int pos[2'000'000];
int lst[50'000'000], nxt[50'000'000], val[50'000'000], vCnt;
inline void addEdge(int x, int y, int v){
    lst[pos[x]] = y, nxt[pos[x]] = ++vCnt, val[pos[x]] = v;
    lst[pos[y]] = x, nxt[pos[y]] = ++vCnt, val[pos[y]] = v;
    pos[x] = nxt[pos[x]], pos[y] = nxt[pos[y]];
}

struct segTree{
    vector<int> vec[1<<22];
    int maxLim[1<<22];

    void push(int i, int l, int r, int x, int v){
        if(l==r){
            vec[i].push_back(v);
            return;
        }
        int m = (l+r)>>1;
        if(x<=m) push(i*2, l, m, x, v);
        else push(i*2+1, m+1, r, x, v);
    }

    void init(int i, int l, int r){
        if(l==r) return;
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
        vec[i].resize(vec[i*2].size() + vec[i*2+1].size());
        merge(vec[i*2].begin(), vec[i*2].end(), vec[i*2+1].begin(), vec[i*2+1].end(), vec[i].begin());
    }

    void work(int i, int l, int r, int s, int e, int lim){
        if(r<s || e<l || vec[i].empty()) return;
        if(s<=l && r<=e){
            if(vec[i][0] >= lim) return;
            addEdge(lim, vec[i][0], 1);
            maxLim[i] = max(maxLim[i], lim);
            return;
        }
        int m = (l+r)>>1;
        work(i*2, l, m, s, e, lim);
        work(i*2+1, m+1, r, s, e, lim);
    }

    void tidy(int i, int l, int r){
        if(l==r || (int)vec[i].size() < 2) return;

        for(int x=0; x<(int)vec[i].size()-1; x++){
            if(vec[i][x+1] >= maxLim[i]) continue;
            addEdge(vec[i][x], vec[i][x+1], 0);
        }

        int m = (l+r)>>1;
        tidy(i*2, l, m);
        tidy(i*2+1, m+1, r);
    }
} tree;

int n;
int A[1000002], B[1000002];
int col[2'000'002];
int ans;

void dfs(int x, int c){
    col[x] = c;
    int v = x;
    while(nxt[v]){
        int y = lst[v], tc = c + val[v] * (c==1 ? 1 : -1);
        if(col[y]){
            if(col[y] != tc) no();
        }
        else dfs(y, tc);
        v = nxt[v];
    }
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d %d", &A[i], &B[i]);
    for(int i=1; i<=n; i++){
        tree.push(1, 1, n*2, B[i], A[i]);
    }
    tree.init(1, 1, n*2);
    for(int i=1; i<=n*2; i++) pos[i] = i;
    vCnt = n*2+1;
    for(int i=1; i<=n; i++){
        tree.work(1, 1, n*2, A[i], B[i], A[i]);
    }
    tree.tidy(1, 1, n*2);

    for(int i=1; i<=n; i++){
        if(col[A[i]]) continue;
        dfs(A[i], 1);
        ans++;
    }
    ll ret = 1;
    for(int i=1; i<=ans; i++) ret = ret * 2 % 1'000'000'007;
    printf("%lld", ret);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
port_facility.cpp:90:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     for(int i=1; i<=n; i++) scanf("%d %d", &A[i], &B[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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