Submission #330112

#	Time	Username	Problem	Language	Result	Execution time	Memory
330112		lohacho	Port Facility (JOI17_port_facility)	C++14	0 / 100	5 ms	6636 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

using LL = long long;
const int MOD = (int)1e9 + 7;
const int NS = (int)2e5 + 4;
int N;
pair<int, int> a[NS];
pair<int, int> tree[NS * 4];

void upd(pair<int, int>&A, int B){
    if(B < A.first){
        A.second = A.first;
        A.first = B;
    }
    else if(B < A.second){
        A.second = B;
    }
}

void push(int num, int s, int e, int pos, int val){
    if(pos < s || pos > e){
        return;
    }
    if(s == e){
        upd(tree[num], val);
        return;
    }
    push(num * 2, s, (s + e) / 2, pos, val);
    push(num * 2 + 1, (s + e) / 2 + 1, e, pos, val);
    tree[num] = tree[num * 2];
    upd(tree[num], tree[num * 2 + 1].first);
    upd(tree[num], tree[num * 2 + 1].second);
}

pair<int, int> get(int num, int s, int e, int fs, int fe){
    if(fe < s || fs > e || fs > fe){
        return {MOD, MOD};
    }
    if(s >= fs && e <= fe){
        return tree[num];
    }
    pair<int, int> l = get(num * 2, s, (s + e) / 2, fs, fe);
    pair<int, int> r = get(num * 2 + 1, (s + e) / 2 + 1, e, fs, fe);
    upd(l, r.first), upd(l, r.second);
    return l;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    for(int i = 0; i < NS * 4; ++i){
        tree[i].first = tree[i].second = MOD;
    }
    cin >> N;
    for(int i = 1; i <= N; ++i){
        cin >> a[i].first >> a[i].second;
    }
    sort(a + 1, a + N + 1, [&](pair<int, int>&A, pair<int, int>&B){return A.second < B.second;});
    int ans = 1;
    for(int i = 1; i <= N; ++i){
        pair<int, int> rv = get(1, 1, NS - 1, a[i].first + 1, a[i].second - 1);
        if(rv.first < a[i].first && rv.second < a[i].first){
            ans = 0; break;
        }
        if(rv.first > a[i].first){
            ans = (ans * 2) % MOD;
        }
        push(1, 1, NS - 1, a[i].second, a[i].first);
    }
    cout << ans;
    return 0;
}

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