제출 #897565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
897565		andrey27_sm	Port Facility (JOI17_port_facility)	C++17	0 / 100	6059 ms	2396 KiB

port_facility

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("arch=icelake-server,avx512f,avx512bw,avx512bitalg,bmi,bmi2")

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
constexpr ll mod = 1e9 + 7;

ll bin_pow(ll base, ll exp)
{
    ll res = 1;
    while (exp){
        if (exp & 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}
int sgt[4000000];
int min_r[4000000];
/*
void update(int v, int tl, int tr, int pos, int val)
{
    if (tl == tr)
        sgt[v] = val;
    else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v * 2, tl, tm, pos, val);
        else
            update(v * 2 + 1, tm + 1, tr, pos, val);
        sgt[v] = sgt[v * 2] + sgt[v * 2 + 1];
    }
}
int get(int v, int l, int r, int tl, int tr)
{
    if (l > tr or tl > r)
        return 0;
    if (tl <= l && r <= tr)
        return sgt[v];
    int m = (l + r) / 2;
    return get(v * 2, l, m, tl, tr) + get(v * 2 + 1, m + 1, r, tl, tr);
}*/
void update(int v,int l,int r,int pos, int val) {
    sgt[pos] = val;
}
int get(int v, int l, int r, int tl, int tr) {
    int sum = 0;
    for(int i = tl;i <= tr;i++) {
        sum+=sgt[i];
    }
    return sum;
}

int main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(nullptr);
    //cout.tie(nullptr);
    ll n;
    cin >> n;
    vector<pair<int,int>> events;
    for (int i = 0; i < n; ++i) {
        int l,r;
        cin >> l >> r;
        events.emplace_back(l,r);
        events.emplace_back(r,l);
    }
    sort(events.begin(),events.end());
    bool is_pos = true;
    int cnt = n;
    set<int> Rs;
    set<int> Ls;
    for(int i = 0;i < 2*n;i++) {
        if(events[i].first < events[i].second) {
            Ls.insert(events[i].first);
            auto it = Rs.insert(events[i].second);
            if(it.first != Rs.begin()) {
                min_r[events[i].first] = *prev(it.first);
            }
            update(1,1,2*n,events[i].first,1);
        }
        else {
            update(1,1,2*n,events[i].second,0);
            Rs.erase(events[i].first);
            auto it = Ls.find(events[i].second);
            if(next(it) != Ls.end()) {
                if(*next(it) < min_r[events[i].second]) {
                    is_pos = false;
                    break;
                }
            }
            Ls.erase(it);
            cnt-=get(1,1,2*n,events[i].second,2*n);
        }
    }
    if(is_pos) {
        cout << bin_pow(2,cnt) << '\n';
    }
    else {
        cout << 0 << '\n';
    }
    return 0;
}

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