Submission #246899

#	Time	Username	Problem	Language	Result	Execution time	Memory
246899		egekabas	Port Facility (JOI17_port_facility)	C++14	0 / 100	5 ms	384 KiB

port_facility

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
const ll mod = 1e9+7;
ll pw(ll x, ll y){
    ll ret = 1;
    while(y){
        if(y%2)
            ret = x*ret%mod;
        y /= 2;
        x = x*x%mod;
    }
    return ret;
}
ll div2;
ll ans = 1;
vector<pair<int, pii>> ev;
pii a[1000009];
int st[1000009];
set<pii> s[3];
int n;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> a[i].ff >> a[i].ss;
        ev.pb({a[i].ff, {i, 1}});
        ev.pb({a[i].ss, {i, 0}});   
    }
    ll div2 = pw(2, mod-2);
    sort(ev.begin(), ev.end());
    for(auto u : ev){
        int id = u.ss.ff;
        if(u.ss.ss == 0){
            s[st[id]].erase({a[id].ss ,id});
            continue;
        }
        auto it0 = s[0].lower_bound({a[id].ss, 0});
        auto it1 = s[1].lower_bound({a[id].ss, 0});
        auto it2 = s[2].lower_bound({a[id].ss, 0});
        int curgroup;
        if(it0 == s[0].begin() && it1 == s[1].begin())
            curgroup = 2;
        else if(it0 == s[0].begin())
            curgroup = 0;
        else if(it1 == s[1].begin())
            curgroup = 1;
        else{ 
            cout << 0;
            return 0;
        }
        if(it2 == s[2].begin()){
            st[id] = curgroup;
            s[curgroup].insert({a[id].ss, id});
            if(curgroup == 2)
                ans = ans*2%mod;
        }
        else{
            if(curgroup == 2){
                ans = ans*2%mod;
                curgroup = 0;
            }
            st[id] = curgroup;
            s[curgroup].insert({a[id].ss, id});
            while(it2 != s[2].begin()){
                --it2;
                ans = ans*div2%mod;
                st[it2->ss] = curgroup^1;
                s[curgroup^1].insert(*it2);
                it2 = s[2].erase(it2);
            }
        }
    }
    cout << ans << '\n';
}

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