Submission #204065

#	Time	Username	Problem	Language	Result	Execution time	Memory
204065		ToMmyDong	Port Facility (JOI17_port_facility)	C++11	0 / 100	36 ms	47352 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;++i)
#define SZ(i) int(i.size())
#define eb emplace_back
#define ALL(i) i.begin(),i.end()
#define X first
#define Y second
#ifdef tmd
#define IOS()
#define debug(...) fprintf(stderr,"#%d: %s = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
template<typename It> ostream& _printRng(ostream &os,It bg,It ed)
{
    os<<"{";
    for(It it=bg;it!=ed;it++) {
        os<<(it==bg?"":",")<<*it;
    }
    os<<"}";
    return os;
}
template<typename T> ostream &operator << (ostream &os,vector<T> &v){return _printRng(os,v.begin(), v.end());}
template<typename T> void pary(T bg, T ed){_printRng(cerr,bg,ed);cerr<<endl;}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define debug(...)
#define pary(...)
#endif

const int MAXN = 1000006;
const ll MOD = 1000000007;

int n;
pair<int,int> rng[MAXN];
bool isTwo[MAXN];
vector<int> check[MAXN*2];

bool isZero () {
    vector<int> lstk = {MOD}, rstk = {MOD};
    REP (i, n) {
        while (lstk.back() < rng[i].X) {
            lstk.pop_back();
        }
        while (rstk.back() < rng[i].X) {
            rstk.pop_back();
        }
//        debug(lstk, rstk);

        if (lstk.back() > rstk.back()) {
            swap(lstk, rstk);
        }

        if (lstk.back() > rng[i].Y) {
            lstk.eb(rng[i].Y);
        } else if (rstk.back() > rng[i].Y) {
            rstk.eb(rng[i].Y);
        } else {
            return true;
        }
    }

    return false;
}
/*********************GoodLuck***********************/
int main () {
    IOS();

    cin >> n;

    REP (i, n) {
        cin >> rng[i].X >> rng[i].Y;
        isTwo[i] = true;
    }

    sort(rng, rng+n);

    if (isZero()) {
        cout << 0 << endl;
        return 0;
    }

    set<int> st;
    REP (i, n) {
        auto ptr = st.lower_bound(rng[i].X);
        if (ptr != st.end() && *ptr < rng[i].Y) {
            isTwo[i] = false;
        }

        ptr = st.lower_bound(rng[i].Y);
        if (ptr != st.end()) {
            check[*ptr].eb(i);
        }

        st.insert(rng[i].Y);
    }

    st.clear();

    int cur = n-1;
    for (int i=n*2; i>=1; i--) {
        for (auto v : check[i]) {
            debug(i, v);
            auto ptr = st.lower_bound(rng[v].X);
            if (ptr != st.end() && *ptr < rng[v].Y) {
                isTwo[v] = false;
            }
        }

        if (cur >= 0 && rng[cur].Y == i) {
            st.insert(rng[cur].X);
            cur--;
        }
    }

    ll ans = 1;
    REP (i, n) {
        if (isTwo[i]) {
            debug(i);
            ans = ans * 2 % MOD;
        }
    }

    cout << ans << endl;
}
/*
3
1 5
2 4
3 6
*/

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