Submission #373543

#	Time	Username	Problem	Language	Result	Execution time	Memory
373543		8e7	Port Facility (JOI17_port_facility)	C++14	100 / 100	4601 ms	164600 KiB

port_facility

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#define ll long long
#define maxn 2000005
#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 mi[4 * maxn], ma[4 * maxn];
void modify(int cur, int l, int r, int ind, int val, int type) {
	if (r <= l) return;
	if (r - l == 1) {
		if (type == 0) mi[cur] = val;
		else ma[cur] = val;
		return;
	}
	int mid = (l + r) / 2;
	if (ind < mid) modify(cur * 2, l, mid, ind, val, type);
	else modify(cur * 2 + 1, mid, r, ind, val, type);
	if (type == 0) mi[cur] = min(mi[cur * 2], mi[cur * 2 + 1]);
	else ma[cur] = max(ma[cur * 2], ma[cur * 2 + 1]);
}
int query(int cur, int l, int r, int ql, int qr, int type) {
	if (r <= l || ql >= r || qr <= l) return type ? -1 : 1<<30;
	if (ql <= l && qr >= r) return type ? ma[cur] : mi[cur];
	int mid = (l + r) / 2;
	if (type) return max(query(cur * 2, l, mid, ql, qr, type), query(cur * 2 + 1, mid, r, ql, qr, type));
	else return min(query(cur * 2, l, mid, ql, qr, type), query(cur * 2 + 1, mid, r, ql, qr, type));
}

int other[maxn], id[maxn], col[maxn];
bool islef[maxn], vis[maxn];

vector<vector<int> > com;

int n;
inline void del(int val, int type) {
	//cout << a[id[val]].l << " " << a[id[val]].r << endl;
	//cout << other[val] << " " << (type ? -1 : 1<<30) << endl;
	if (vis[id[val]]) return;
	vis[id[val]] = 1;
	modify(1, 0, 2 * n, other[val], type ? -1 : 1<<30, type);
	modify(1, 0, 2 * n, val, type ? 1<<30 : -1, type ^ 1);
}

inline bool cmp(int x, int y) {
	return a[x].l < a[y].l;
}
bool poss(vector<int> &x) {
	stack<int> stk;
	sort(x.begin(), x.end(), cmp);
	bool ret = true;
	for (int c = 0;c < 2;c++) {
		for (int i = 0;i < x.size();i++) {
			if (col[x[i]] != c) continue;
			while (stk.size() && a[x[i]].l > stk.top()) stk.pop();
			if (stk.size() && a[x[i]].r > stk.top()) return false;
			else stk.push(a[x[i]].r);
		}
		while (stk.size()) stk.pop();
	}
	return ret;
}
int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for (int i = 0;i < 4 * maxn;i++) mi[i] = 1<<30, ma[i] = -1; //0 based values
    for (int i = 0;i < n;i++) {
    	cin >> a[i].l >> a[i].r, a[i].id = i;
    	a[i].l--, a[i].r--;
    	islef[a[i].l] = 1;
    	other[a[i].l] = a[i].r, other[a[i].r] = a[i].l;
    	id[a[i].l] = id[a[i].r] = i;

    	modify(1, 0, 2 * n, a[i].l, a[i].r, 1);
    	modify(1, 0, 2 * n, a[i].r, a[i].l, 0);
    }
    for (int st = 0;st < n;st++) {
    	if (vis[st]) continue;
    	queue<pii> que;
    	que.push(make_pair(st, 1));
    	vector<int> add;
    	while (que.size()) {
    		int cur = que.front().ff;
    		col[cur] = que.front().ss;
    		que.pop();
    		add.push_back(cur);
    		//cout << cur << endl;
    		del(a[cur].r, 1);
        	int val = query(1, 0, 2 * n, a[cur].l, a[cur].r + 1, 1); //max part
        	while (val > a[cur].r) {
        		//cout << val << endl;
        		del(val, 1);
        		que.push(make_pair(id[val], col[cur] ^ 1));
        		val = query(1, 0, 2 * n, a[cur].l, a[cur].r + 1, 1);
        	}
        	val = query(1, 0, 2 * n, a[cur].l, a[cur].r + 1, 0);
        	while (val < a[cur].l) {
        		//cout << a[id[val]].l << "  " << a[id[val]].r << endl;

        		del(val, 0);
        		que.push(make_pair(id[val], col[cur] ^ 1));
        		val = query(1, 0, 2 * n, a[cur].l, a[cur].r + 1, 0);
        	}
    	}
    	//cout << endl;
    	com.push_back(add);

    }
    ll ans = 1;
    for (int i = 0;i < com.size();i++) {
    	ans = (ans * (poss(com[i]) ? 2 : 0)) % mod;
    	if (ans == 0) break;
    }
    cout << ans << "\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
 */

Compilation message (stderr)

port_facility.cpp: In function 'bool poss(std::vector<int>&)':
port_facility.cpp:75:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |   for (int i = 0;i < x.size();i++) {
      |                  ~~^~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:132:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for (int i = 0;i < com.size();i++) {
      |                    ~~^~~~~~~~~~~~

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