Submission #539017

#	Time	Username	Problem	Language	Result	Execution time	Memory
539017		MilosMilutinovic	Port Facility (JOI17_port_facility)	C++14	100 / 100	1916 ms	209796 KiB

port_facility

#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MOD = 1000000007;

int n, a[1000005], b[1000005], col[1000005];
PII arr[4000005];
vector<int> G[1000005];

struct segt
{
	#define data_t pair<PII, PII>
	data_t data[8000005];
	void build(int cv = 1, int cl = 1, int cr = 2 * n) {
		if(cl == cr) {
			data[cv].first = data[cv].second = arr[cl];
			return;
		}
		int mid = cl + cr >> 1;
		build(cv << 1, cl, mid);
		build(cv << 1 | 1, mid + 1, cr);
		data[cv].first = min(data[cv << 1].first, data[cv << 1 | 1].first);
		data[cv].second = max(data[cv << 1].second, data[cv << 1 | 1].second);
	}
	data_t query(int l, int r, int cv = 1, int cl = 1, int cr = 2 * n) {
		if(cl > r || l > cr) return MP(MP(MOD, 0), MP(-1, 0));
		if(l <= cl && cr <= r) return data[cv];
		int mid = cl + cr >> 1;
		data_t ls = query(l, r, cv << 1, cl, mid);
		data_t rs = query(l, r, cv << 1 | 1, mid + 1, cr);
		return MP(min(ls.first, rs.first), max(ls.second, rs.second));
	}
} tre;

int power(int x, int y)
{
	int ret = 1;
	while(y --) ret = ret * x, ret %= MOD;
	return ret;
}

bool inter(int l1, int r1, int l2, int r2)
{
	if(r1 < l2) return false;
	if(r2 < l1) return false;
	if(l1 <= l2 && r2 <= r1) return false;
	if(l2 <= l1 && r1 <= r2) return false;
	return true;
}

void NO()
{
	printf("0");
	exit(0);
}

void dfs(int v) {
	rep(i, G[v].size()) {
		int u = G[v][i];
		if(col[u] == -1) col[u] = col[v] ^ 1, dfs(u);
		if(col[u] == col[v]) NO();
	}
}

void addEdge(int x, int y)
{
	G[x].push_back(y);
	G[y].push_back(x);
}

int main()
{
	scanf("%d", &n);
	rep(i, n) {
		scanf("%d%d", &a[i], &b[i]);
		arr[a[i]] = MP(b[i], i);
		arr[b[i]] = MP(a[i], i);
	}
	tre.build();
	rep(i, n) {
		int idL = tre.query(a[i], b[i]).first.second;
		int idR = tre.query(a[i], b[i]).second.second;
		if(inter(a[idL], b[idL], a[i], b[i])) addEdge(i, idL);
		if(inter(a[idR], b[idR], a[i], b[i])) addEdge(i, idR);
	}
	rep(i, n) col[i] = -1;
	int cnt = 0;
	rep(i, n) if(col[i] == -1) col[i] = 0, dfs(i), ++ cnt;
	printf("%d", power(2, cnt));
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In member function 'void segt::build(int, int, int)':
port_facility.cpp:24:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
port_facility.cpp: In member function 'std::pair<std::pair<int, int>, std::pair<int, int> > segt::query(int, int, int, int, int)':
port_facility.cpp:33:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   33 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
port_facility.cpp:80:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |   scanf("%d%d", &a[i], &b[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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