Submission #131900

#	Time	Username	Problem	Language	Result	Execution time	Memory
131900		songc	Port Facility (JOI17_port_facility)	C++14	100 / 100	5880 ms	146936 KiB

port_facility

#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;

int N, cnt, ans;
int A[1010101], B[1010101], C[1010101], P[2020202];
pii Max[8080808], Min[8080808];
vector<int> St1, St2;

void updMax(int id, int s, int e, int t, pii v){
    if (e < t || t < s) return;
    if (s == e){
        Max[id] = v;
        return;
    }
    int mid=(s+e)/2;
    updMax(id*2, s, mid, t, v);
    updMax(id*2+1, mid+1, e, t, v);
    Max[id] = max(Max[id*2], Max[id*2+1]);
}

void updMin(int id, int s, int e, int t, pii v){
    if (e < t || t < s) return;
    if (s == e){
        Min[id] = v;
        return;
    }
    int mid=(s+e)/2;
    updMin(id*2, s, mid, t, v);
    updMin(id*2+1, mid+1, e, t, v);
    Min[id] = min(Min[id*2], Min[id*2+1]);
}

pii MaxQ(int id, int s, int e, int ts, int te){
    if (e < ts || te < s) return pii(0, 0);
    if (ts <= s && e <= te) return Max[id];
    int mid = (s+e)/2;
    return max(MaxQ(id*2, s, mid, ts, te), MaxQ(id*2+1, mid+1, e, ts, te));
}

pii MinQ(int id, int s, int e, int ts, int te){
    if (e < ts || te < s) return pii(1234567890, 0);
    if (ts <= s && e <= te) return Min[id];
    int mid = (s+e)/2;
    return min(MinQ(id*2, s, mid, ts, te), MinQ(id*2+1, mid+1, e, ts, te));
}

void dfs(int u, int c){
    C[u] = c;
    while (1){
        pii t = MaxQ(1, 1, 2*N, A[u], B[u]);
        if (t.first > B[u]){
            updMax(1, 1, 2*N, A[t.second], pii(0, 0));
            updMin(1, 1, 2*N, B[t.second], pii(1234567890, 0));
            dfs(t.second, -c);
            continue;
        }

        t = MinQ(1, 1, 2*N, A[u], B[u]);
        if (t.first < A[u]){
            updMax(1, 1, 2*N, A[t.second], pii(0, 0));
            updMin(1, 1, 2*N, B[t.second], pii(1234567890, 0));
            dfs(t.second, -c);
            continue;
        }
        return;
    }
}

int main(){
    scanf("%d", &N);
    fill(Min, Min+8*N, pii(1234567890, 0));
    for (int i=1; i<=N; i++) {
        scanf("%d %d", &A[i], &B[i]);
        updMin(1, 1, 2*N, B[i], pii(A[i], i));
        updMax(1, 1, 2*N, A[i], pii(B[i], i));
        P[A[i]] = P[B[i]] = i;
    }
    for (int i=1; i<=N; i++) if (!C[i]) cnt++, dfs(i, 1);
    for(int i=1; i<=2*N; i++){
        if (!St1.empty() && St1.back() == P[i]) St1.pop_back();
        else if (!St2.empty() && St2.back() == P[i]) St2.pop_back();
        else{
            if (C[P[i]] == 1) St1.push_back(P[i]);
            else St2.push_back(P[i]);
        }
    }
    if (!St1.empty() || !St2.empty()){
        puts("0");
        return 0;
    }
    ans = 1;
    for (int i=1; i<=cnt; i++) ans = ans * 2 % MOD;
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
port_facility.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &A[i], &B[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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