Submission #533367

#	Time	Username	Problem	Language	Result	Execution time	Memory
533367		pooyashams	Port Facility (JOI17_port_facility)	C++14	100 / 100	3675 ms	310740 KiB

port_facility

#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

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

const int maxn = 1e6+10;
const int mod = 1e9+7;
const int inf = 1e9+42069;

inline int bpow(int x, int y)
{
	int ans = 1;
	while(y > 0)
	{
		if(y & 1)
			ans = 1ll*ans*x % mod;
		x = 1ll*x*x % mod;
		y >>= 1;
	}
	return ans;
}

int lft[maxn];
int rit[maxn];
int owner[maxn*2];
bool vis[maxn];
vector<int> G[maxn];
bool col[maxn];

#define lc (v<<1)
#define rc (lc|1)

struct mfsgt
{
	vector<int> vals;
	int (*mf)(int, int);
	int n;
	int d;
	mfsgt(){};
	mfsgt(int _n, int (*_mf)(int,int), int _d)
	{
		mf = _mf;
		n = _n;
		d = _d;
		vals = vector<int>(4*n, d);
	}
	inline void upd(int v)
	{
		vals[v] = (*mf)(vals[lc], vals[rc]);
	}
	void ass(int l, int r, int p, int x, int v)
	{
		if(r - l == 1)
			return (void)(vals[v] = x);
		int m = (l+r) / 2;
		if(p < m)
			ass(l, m, p, x, lc);
		else
			ass(m, r, p, x, rc);
		upd(v);
	}
	int get(int l, int r, int s, int e, int v)
	{
		if(e <= l or r <= s) return d;
		if(s <= l and r <= e) return vals[v];
		int m = (l+r) / 2;
		return (*mf)(get(l, m, s, e, lc), get(m, r, s, e, rc));
	}
	inline void ass(int p, int x)
	{
		return ass(0, n, p, x, 1);
	}
	inline int get(int s, int e)
	{
		return get(0, n, s, e, 1);
	}
} mnseg, mxseg;

inline int min(int x, int y)
{
	return std::min(x, y);
}
inline int max(int x, int y)
{
	return std::max(x, y);
}

inline int getbef(int l, int r) // [l, r)
{
	int x = mnseg.get(l, r);
	if(x == inf or x >= l) return -1;
	return owner[x];
}
inline int getaft(int l, int r)
{
	int y = mxseg.get(l, r);
	if(y == -1 or y <= r) return -1;
	return owner[y];
}
inline int getany(int l, int r)
{
	int x = getbef(l, r);
	if(x != -1)
		return x;
	x = getaft(l, r);
	return x;
}

void mfdfs(int v, bool c)
{
	//cerr << "in " << v << endl;
	if(vis[v]) return (void)(cerr << "ridim " << v << endl);
	vis[v] = true;
	col[v] = c;
	mnseg.ass(rit[v], inf);
	mxseg.ass(lft[v], -1);
	int u = getany(lft[v]+1, rit[v]);
	while(u != -1)
	{
		G[v].push_back(u);
		G[u].push_back(v);
		mfdfs(u, !c);
		u = getany(lft[v]+1, rit[v]);
	}
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	mnseg = mfsgt(2*n, min, inf); // write lft[i] in rit[i] others are inf
	mxseg = mfsgt(2*n, max, -1); // write rit[i] in lft[i] others are -1
	for(int i = 0; i < n; i++)
	{
		cin >> lft[i] >> rit[i];
		lft[i]--; rit[i]--;
		owner[lft[i]] = i;
		owner[rit[i]] = i;
		mnseg.ass(rit[i], lft[i]);
		mxseg.ass(lft[i], rit[i]);
	}
	//for(int i = 0; i < 2*n; i++) cerr << mnseg.get(i, i+1) << " "; cerr << endl;
	//for(int i = 0; i < 2*n; i++) cerr << mxseg.get(i, i+1) << " "; cerr << endl;
	int cmpcnt = 0;
	for(int i = 0; i < n; i++)
	{
		if(!vis[i])
		{
			cmpcnt++;
			//cerr << "starting " << i << endl;
			mfdfs(i, 0);
		}
	}
	//for(int i = 0; i < n; i++) cerr << col[i] << " "; cerr << endl;
	stack<int> mfst[2];
	for(int i = 0; i < 2*n; i++)
	{
		int v = owner[i];
		if(i == lft[v])
		{
			mfst[col[v]].push(v);
		}
		else
		{
			if(mfst[col[v]].empty() or mfst[col[v]].top() != v)
			{
				cout << 0 << endl;
				return 0;
			}
			mfst[col[v]].pop();
		}
	}
	cout << bpow(2, cmpcnt) << endl;
	return 0;
}

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