Submission #373435

#	Time	Username	Problem	Language	Result	Execution time	Memory
373435		8e7	Port Facility (JOI17_port_facility)	C++14	0 / 100	13 ms	19948 KiB

port_facility

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <stack>
#define ll long long
#define maxn 1000005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;


struct obj{
	int l, r, id;
	obj() {
		l = 0, r = 0, id = 0;
	}
	obj(int a, int b, int c) {
		l = a, r = b, id = c;
	}
};
obj a[maxn];
int ma[maxn];
inline bool cmp1(obj x, obj y) {
	return x.l < y.l;
}
inline bool cmp2(obj x, obj y) {
	return x.r > y.r;
}

int bit[2 * maxn];
void modify(int ind, int val) {
	for (;ind < 2 * maxn;ind += ind & (-ind)) bit[ind] = max(bit[ind], val);
}
int query(int ind) {
	int ret = 0;
	for (;ind > 0;ind -= ind & (-ind)) ret = max(ret, bit[ind]);
	return ret;
}

stack<obj> stk;
int par[maxn];
int find(int x) {
	return x == par[x] ? x : par[x] = find(par[x]);
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) cin >> a[i].l >> a[i].r, a[i].id = i, par[i] = i;
    sort(a, a + n, cmp1);

    int poss = 1;
    for (int i = 0;i < n;i++) {
    	ma[a[i].id] = query(a[i].r);
    	//cout << a[i].l << " " << a[i].r << " " << ma[a[i].id] << endl;
    	modify(a[i].r, a[i].r);
    }
    for (int i = 0;i < 2 * maxn;i++) bit[i] = 2 * maxn - 2 * n - 1;
    sort(a, a + n, cmp2);
    for (int i = 0;i < n;i++) {
    	//cout << a[i].l << " " << a[i].r << endl;
    	int val = query(2 * maxn - a[i].l);
    	if (2 * maxn - val < ma[a[i].id]) {
    		poss = 0;
    		break;
    	}
    	modify(2 * maxn - a[i].l, 2 * maxn - a[i].l);
    }

    if (poss) {
    	reverse(a, a + n);

    	int ans = n;
    	for (int ti = 0;ti < 2;ti++) {
        	for (int i = 0;i < n;i++) {
        		while (stk.size() && a[i].l < stk.top().l) stk.pop();
        		if (stk.size() && stk.top().r > a[i].l) {
        			if (find(a[i].id) != find(stk.top().id)) {
        				//cout << a[i].id << " " << stk.top().id << endl;
        				par[find(a[i].id)] = find(stk.top().id);
        				ans--;
        			}
        		}
        		stk.push(a[i]);
        	}

        	for (int i = 0;i < n;i++) {
        		a[i].l = 2 * maxn - a[i].l, a[i].r = 2 * maxn - a[i].r, swap(a[i].l, a[i].r);
        	}
        	reverse(a, a + n);
    	}
    	ll out = 1;
    	for (int i = 0;i < ans;i++) out = out * 2 % mod;
    	cout << out << "\n";
    } else {
    	cout << 0 << "\n";
    }

}
/*
4
1 3
2 5
4 8
6 7

3
1 4
2 5
3 6

5
1 4
2 10
6 9
7 8
3 5

8
1 15
2 5
3 8
4 6
14 16
7 9
10 13
11 12

5
2 5
4 7
6 8
1 9
3 10
 */

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