Submission #66779

#	Time	Username	Problem	Language	Result	Execution time	Memory
66779		elitewantsyou	Port Facility (JOI17_port_facility)	C++14	0 / 100	3 ms	376 KiB

port_facility

#include <bits/stdc++.h>

#define fi first
#define se second
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );

const long long N = 2000100;
const long long Q = N * 30;
const long long mod = 1e9 + 7;
const long long MAGIC = 30;

using namespace std;

int n;
int f[N];
bool t[2][4 * N];

void upd(int tp, int x, int l, int r, int g)
{
        t[tp][x] = 1;
        if(l == r){
                return;
        }
        int m = (l + r) / 2;
        if(g <= m){
                upd(tp, x * 2, l, m, g);
        }
        else{
                upd(tp, x * 2 + 1, m + 1, r, g);
        }
}

bool get(int tp, int x, int l, int r, int tl, int tr)
{
        if(tl > tr){
                return 0;
        }
        if(l == tl && r == tr){
                return t[tp][x];
        }
        int m = (l + r) / 2;
        return get(tp, x * 2, l, m, tl, min(m, tr)) | get(tp, x * 2 + 1, m + 1, r, max(m + 1, tl), tr);
}

void solve()
{
        cin >> n;
        for(int i = 1; i <= n; i++){
                int l, r;
                cin >> l >> r;
                f[l] = r;
        }
        long long ans = 1;
        n += n;
        for(int i = 1; i <= n; i++){
                if(f[i] == 0){
                        continue;
                }
                int f1 = get(0, 1, 1, n, i, f[i]), f2 = get(1, 1, 1, n, i, f[i]);
                if(f1 && f2){
                        cout << 0 << "\n";
                        return;
                }
                else if(!f1){
                        if(!f2){
                                ans += ans;
                                if(ans >= mod){
                                        ans -= mod;
                                }
                        }
                        upd(0, 1, 1, n, f[i]);
                }
                else{
                        upd(1, 1, 1, n, f[i]);
                }
        }
        cout << ans << "\n";
}

bool mtest = false; int main()
{
        //fin("input.txt");
        //fout("output.txt");
        //fin("island.in");
        //fout("island.out");
        ios_base::sync_with_stdio(0);
        int TE = 1;
        if(mtest)
                cin >> TE;
        while(TE--)
                solve();
        return 0;
}

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