Submission #62600

#	Time	Username	Problem	Language	Result	Execution time	Memory
62600		zadrga	Port Facility (JOI17_port_facility)	C++14	78 / 100	6075 ms	73012 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF ((int) 1e9)
#define MOD (1000 * 1000 * 1000 + 7)
#define maxn 1000111

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

int ind[2 * maxn], s[maxn], e[maxn], col[maxn];
int n;

struct seg{
	int seg[4 * maxn];

	void build(){
		for(int i = 0; i < 4 * maxn; i++)
			seg[i] = -INF;
	}

	void update(int x, int l, int d, int i, int j){
		if(l > d || d < i || i < l)
			return;
		if(l == d && l == i){
			seg[x] = j;
			return;
		}
		int mid = (l + d) / 2;
		update(2 * x, l, mid, i, j);
		update(2 * x + 1, mid + 1, d, i, j);
		seg[x] = max(seg[2 * x], seg[2 * x + 1]);
	}

	int query(int x, int l, int d, int i, int j){
		if(l > d || d < i || j < l)
			return -INF;
		if(i <= l && d <= j)
			return seg[x];

		int mid = (l + d) / 2;
		int ret = query(2 * x, l, mid, i, j);
		ret = max(ret, query(2 * x + 1, mid + 1, d, i, j));
		return ret;
	}
}seg1, seg2;

void DFS(int x, int c){
	col[x] = c;
	while(1){
		int t = seg1.query(1, 1, 2 * n, s[x] + 1, e[x] - 1);
		if(t <= e[x])
			break;

		int v = ind[t];
		seg1.update(1, 1, 2 * n, s[v], -1);
		seg2.update(1, 1, 2 * n, e[v], -INF);
		DFS(v, 3 - c);
	}

	while(1){
		int t = -seg2.query(1, 1, 2 * n, s[x] + 1, e[x] - 1);
		if(t >= s[x])
			break;

		int v = ind[t];
		seg1.update(1, 1, 2 * n, s[v], -1);
		seg2.update(1, 1, 2 * n, e[v], -INF);
		DFS(v, 3 - c);
	}
}

bool check(vector<pii> &v){
	sort(v.begin(), v.end());
	stack<pii> st;
	for(int i = 0; i < v.size(); i++){
		while(!st.empty() && st.top().se < v[i].fi)
			st.pop();

		if(!st.empty() && st.top().se > v[i].fi && st.top().se < v[i].se)
			return 0;

		st.push(v[i]);
	}
	return 1;
}

int main(){
	scanf("%d", &n);
	seg1.build();
	seg2.build();
	for(int i = 1; i <= n; i++){
		scanf("%d%d", s + i, e + i);
		ind[s[i]] = ind[e[i]] = i;
		seg1.update(1, 1, 2 * n, s[i], e[i]);
		seg2.update(1, 1, 2 * n, e[i], -s[i]);
	}

	ll ans = 1;
	for(int i = 1; i <= 2 * n; i++){
		if(!col[ind[i]]){
			ans = (ans * 2LL) % MOD;
			seg1.update(1, 1, 2 * n, s[ind[i]], -1);
			seg2.update(1, 1, 2 * n, e[ind[i]], -INF);
			DFS(ind[i], 1);
		}
	}

	vector<pii> l, r;
	for(int i = 1; i <= n; i++){
		if(col[i] == 1)
			l.pb(mp(s[i], e[i]));
		else
			r.pb(mp(s[i], e[i]));
	}

	if(!check(l) || !check(r))
		ans = 0;

	printf("%lld\n", ans);

	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'bool check(std::vector<std::pair<int, int> >&)':
port_facility.cpp:82:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v.size(); i++){
                 ~~^~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
port_facility.cpp:99:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", s + i, e + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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