Submission #332263

#	Time	Username	Problem	Language	Result	Execution time	Memory
332263		LucaDantas	Port Facility (JOI17_port_facility)	C++17	22 / 100	6066 ms	7580 KiB

port_facility

#include<bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;

template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '['; string sep = ""; for (const auto &x : v) os << sep << x, sep = ", "; return os << ']'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, const set<A> &s) { os << '{'; string sep = ""; for (const auto &x : s) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const map<A, B> &m) { os << '{'; string sep = ""; for (const auto &x : m) os << sep << x.first << " -> " << x.second, sep = ", "; return os << '}'; }
template<typename A> ostream& operator<<(ostream &os, priority_queue<A> q) { os << '{'; string sep = ""; while(q.size()) os << sep << q.top(), q.pop(), sep = ", "; return os << '}'; }

#ifdef MY_DEBUG_FLAG
void debug() { cerr << endl; }
template<typename Ini, typename... Fim> void debug(Ini I, Fim... F) { cerr << I; if(sizeof...(F)) cerr << ", "; debug(F...);}
#define db(...) cerr << "DEBUG (" << #__VA_ARGS__ << ") == ", debug(__VA_ARGS__)
#else
#define db(...)
#endif


#define ss second
#define ff first
#define pb push_back

constexpr int maxn = 1e6+10, mod = 1000000007;

struct DSU
{
	int pai[maxn], peso[maxn], cor[maxn], cc, bip;
	void init(int n) {
		cc = n; bip = 1;
		for(int i = 1; i <= n; i++)
			pai[i] = i, peso[i] = cor[i] = 0;
	}
	int find(int x, int& c) {
		while(x != pai[x])
			c ^= cor[x], x = pai[x];
		return x;
	}
	void join(int a, int b) {
		if(a == b) return;
		int c1 = 0, c2 = 0;
		// printf("%d %d\n", a, b);
		a = find(a, c1), b = find(b, c2);
		if(a == b && c1 == c2) return (void)(bip = 0);
		if(a != b) {
			--cc;
			if(peso[a] < peso[b])
				swap(a, b);
			pai[b] = a;
			peso[a] += peso[b];
			cor[b] = 1^c1^c2;
		}
	}
} dsu;

int power(int b, int e) {
	int ans = 1;
	while(e) {
		if(e&1) ans = (int)(1ll * ans * b % mod);
		b = (int)(1ll * b * b % mod);
		e >>= 1;
	}
	return ans;
}

struct Event
{
	int a, b;
	bool operator<(Event x) {return b<x.b;}
	friend ostream& operator<<(ostream& os, Event a) {return os << make_pair(a.a, a.b);}
} evt[maxn+1];

int prox[maxn], pos[2*maxn], cnt;

int find(int x, int id) {
	// printf("x, pos[x], id, %d %d %d %d %d\n", x, pos[x], id, evt[pos[x]].a, evt[id].b);
	if(x == maxn || x > evt[id].b) return maxn;
	dsu.join(pos[x], id);
	// assert(++cnt < 10);
	return prox[evt[x].a] = find(prox[evt[pos[x]].a], id);
}

int main() {
	int n; scanf("%d", &n);
	dsu.init(n);
	for(int i = 1, a, b; i <= n; ++i)
		scanf("%d %d", &a, &b), evt[i] = {a, b};
	for(int i = 1; i <= 2*n; i++)
		prox[i] = maxn;
	sort(evt+1, evt+1+n); reverse(evt+1, evt+1+n);
	for(int i = 1; i <= n; i++)
		pos[evt[i].a] = i;
	// for(int i = 1; i <= n; i++)
	// 	printf("%d %d\n", evt[i].a, evt[i].b);
	set<pii> st;
	for(int i = 1; i <= n; i++) {
		while(st.size() && (*st.rbegin()).ff > evt[i].b)
			st.erase(*st.rbegin());
		// db(st, evt[i]);
		auto it = st.upper_bound({evt[i].a, 0});
		if(it!=st.end())
			/*db(*it),*/ find((*it).ff, i);
		st.insert({evt[i].a, i});
		for(int j = 1; j < evt[i].a; j++)
			prox[j] = min(prox[j], evt[i].a);
	}
	// printf("%d %d\n", dsu.bip, dsu.cc);
	printf("%d\n", dsu.bip?power(2, dsu.cc):0);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
port_facility.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |   scanf("%d %d", &a, &b), evt[i] = {a, b};
      |   ~~~~~^~~~~~~~~~~~~~~~~

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