Submission #332277

#	Time	Username	Problem	Language	Result	Execution time	Memory
332277		LucaDantas	Port Facility (JOI17_port_facility)	C++17	22 / 100	6089 ms	40812 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];

struct SegmentTree
{
	int tree[4*maxn], lazy[4*maxn];
	SegmentTree() {
		for(int i = 0; i < 4*maxn; i++)
			tree[i] = lazy[i] = maxn;
	}
	void flush(int node, int i, int j) {
		if(lazy[node] == maxn) return;
		if(i != j)
			lazy[2*node] = min(lazy[2*node], lazy[node]),
			lazy[2*node+1] = min(lazy[2*node+1], lazy[node]);
		tree[node] = min(tree[node], lazy[node]);
		lazy[node] = maxn;
	}
	void upd_lazy(int node, int i, int j, int r, int v) {
		flush(node, i, j);
		if(i > r) return;
		if(j <= r) return (void)(lazy[node] = v, flush(node, i, j));
		int m = (i+j) >> 1;
		upd_lazy(2*node, i, m, r, v); upd_lazy(2*node+1, m+1, j, r, v);
		tree[node] = max(tree[2*node], tree[2*node+1]);
	}
	void upd(int node, int i, int j, int pos, int v) {
		flush(node, i, j);
		if(i == j) return (void)(tree[node] = v);
		int m = (i+j) >> 1;
		if(pos <= m) upd(2*node, i, m, pos, v);
		else upd(2*node+1, m+1, j, pos, v);
		tree[node] = max(tree[2*node], tree[2*node+1]);
	}
	int query(int node, int i, int j, int pos) {
		flush(node, i, j);
		if(i == j) return tree[node];
		int m = (i+j) >> 1;
		if(pos <= m) return query(2*node, i, m, pos);
		return query(2*node+1, m+1, j, pos);
	}
} seg;

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

void find(int x, int id) {
	while(x <= evt[id].b) {
		dsu.join(pos[x], id);
		int go = seg.query(1, 1, 2*n, x);
		seg.upd(1, 1, 2*n, x, maxn);
		x = go;
	}
}

int main() {
	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;
	set<pii> st;
	for(int i = 1; i <= n; i++) {
		while(st.size() && (*st.rbegin()).ff > evt[i].b)
			st.erase(*st.rbegin());
		auto it = st.upper_bound({evt[i].a, 0});
		if(it!=st.end())
			find((*it).ff, i);
		seg.upd_lazy(1, 1, 2*n, evt[i].a-1, evt[i].a);
		st.insert({evt[i].a, i});
	}
	printf("%d\n", dsu.bip?power(2, dsu.cc):0);
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:126:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  126 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
port_facility.cpp:129:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  129 |   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