Submission #211279

#	Time	Username	Problem	Language	Result	Execution time	Memory
211279		mode149256	Port Facility (JOI17_port_facility)	C++14	0 / 100	5 ms	384 KiB

port_facility

/*input
3
1 4
2 5
3 6

5
1 4
2 10
6 9
7 8
3 5

8
1 15
2 5
3 8
4 6
14 16
7 9
10 13
11 12
*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}

vi rankas;
vi p;

int findSet(int i) { return (p[i] == i) ? i : (p[i] = findSet(p[i])); }
bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
void unionSet(int i, int j) {
	if (isSameSet(i, j)) {
		printf("0\n");
		exit(0);
	}

	int x = findSet(i), y = findSet(j);
	if (rankas[x] > rankas[y]) p[y] = x;
	else {
		p[x] = y;
		if (rankas[x] == rankas[y]) rankas[y]++;
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	cin >> N;

	p = vi(2 * N + 1); for (int i = 0; i <= 2 * N; i++) p[i] = i;
	rankas = vi(2 * N + 1, 0);

	vpi poros;
	vi kitas(2 * N + 1);
	for (int i = 0; i < N; ++i)
	{
		int a, b;
		cin >> a >> b;
		kitas[a] = b;
		kitas[b] = a;
		unionSet(a, b);
		poros.emplace_back(a, b);
	}

	ll ats = 1;

	sort(poros.begin(), poros.end());

	set<int> visos;
	set<int> reikalingos;

	for (int i = 1; i <= 2 * N; i++) {
		if (i < kitas[i]) {
			int a = i;
			int b = kitas[i];

			if (reikalingos.empty()) {
				visos.insert(b);
				reikalingos.insert(b);
				continue;
			}

			auto it = reikalingos.begin();
			int prad = *it;

			if (b < prad) reikalingos.insert(b);
			else {
				while (it != reikalingos.end() and * it < b) {
					// printf("jungiu i = %d, it = %d\n", i, *it);
					unionSet(i, *it);

					auto prev = it;
					it = next(it);

					reikalingos.erase(prev);
				}
				reikalingos.insert(prad);
			}

			visos.insert(b);
		} else {
			visos.erase(i);
			reikalingos.erase(i);
			if (visos.size())
				reikalingos.insert(*visos.begin());
		}
	}

	vb buvo(2 * N + 1, false);
	for (int i = 1; i <= 2 * N; ++i)
	{
		if (!buvo[findSet(i)]) ats = (ats * 2) % MOD;
		buvo[findSet(i)] = true;
	}
	printf("%lld\n", ats);
}

/* Look for:
* special cases (n=1?)
* overflow (ll vs int?)
* the exact constraints (multiple sets are too slow for n=10^6 :( )
* array bounds
*/

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:124:8: warning: unused variable 'a' [-Wunused-variable]
    int a = i;
        ^

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