제출 #45617

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45617		maksim_gaponov	Port Facility (JOI17_port_facility)	C++14	78 / 100	6101 ms	239464 KiB

port_facility

#define _CRT_SECURE_NO_WARNINGS
#ifdef _DEBUG
#define FILE_IN "input.txt"
#define FILE_OUT "output.txt"
#endif
#include <iostream>
#include <cstdlib>
#include <climits>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
typedef long long ll;
const ll mod = 1000000007;

void openFiles() {
#ifdef _DEBUG
	assert(freopen(FILE_IN, "r", stdin));
	assert(freopen(FILE_OUT, "w", stdout));
#endif
}

void IOoptimize() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}
 
const int MAXN = 1000000 + 10;
pair<int, int> max_end[5 * 2 * MAXN];
pair<int, int> min_start[5 * 2 * MAXN];
int color[MAXN];

struct Action {
	int id;
	int time;
	bool type;

	Action(int id, int time, bool type) : id(id), time(time), type(type) {}
};

vector<Action> actions;

bool operator<(const Action& a1, const Action& a2) {
	return a1.time < a2.time;
}

bool get_bit(int mask, int i) {
	return mask & (1 << i);
}

void update_ends(int x, int l, int r, int i, pair<int, int> val) {
	if (l > i || r <= i)
		return;
	if (r - l == 1) {
		max_end[x] = val;
		return;
	}
	int c = (l + r) / 2;
	update_ends(2 * x + 1, l, c, i, val);
	update_ends(2 * x + 2, c, r, i, val);
	max_end[x] = max(max_end[2 * x + 1], max_end[2 * x + 2]);
}

void update_starts(int x, int l, int r, int i, pair<int, int> val) {
	if (l > i || r <= i)
		return;
	if (r - l == 1) {
		min_start[x] = val;
		return;
	}
	int c = (l + r) / 2;
	update_starts(2 * x + 1, l, c, i, val);
	update_starts(2 * x + 2, c, r, i, val);
	min_start[x] = min(min_start[2 * x + 1], min_start[2 * x + 2]);
}

pair<int, int> query_ends(int x, int l, int r, int ql, int qr) {
	if (l >= qr || r <= ql)
		return {-1, -1};
	if (ql <= l && r <= qr)
		return max_end[x];
	int c = (l + r) / 2;
	return max(
		query_ends(2 * x + 1, l, c, ql, qr),
		query_ends(2 * x + 2, c, r, ql, qr)
	);
}

pair<int, int> query_starts(int x, int l, int r, int ql, int qr) {
	if (l >= qr || r <= ql)
		return {5 * MAXN, -1};
	if (ql <= l && r <= qr)
		return min_start[x];
	int c = (l + r) / 2;
	return min(
		query_starts(2 * x + 1, l, c, ql, qr),
		query_starts(2 * x + 2, c, r, ql, qr)
	);
}

int main() {
	openFiles();
	IOoptimize();
	memset(color, 0, sizeof(color));
	int n;
	cin >> n;
	for (int i = 0; i < 5 * 2 * n; i++) {
		max_end[i] = {-1, -1};
		min_start[i] = {5 * MAXN, -1};
	}
	vector<pair<int, int>> segments;
	for (int i = 0; i < n; i++) {
		int time1, time2;
		cin >> time1 >> time2;
		time1--;
		time2--;
		segments.push_back({time1, time2});
		update_starts(0, 0, 2 * n, time2, {time1, i});
		update_ends(0, 0, 2 * n, time1, {time2, i});
		actions.push_back(Action(i, time1, true));
		actions.push_back(Action(i, time2, false));
	}
	sort(actions.begin(), actions.end());
	//cout << max_end[0].second << "\n";
	//cout << query_ends(0, 0, 2 * n, 0, 2 * n).second << "\n";
	//return 0;
	ll ans = 1;
	set<int> s;
	for (int i = 0; i < n; i++)
		s.insert(i);
	//cout << query_starts(0, 0, 2 * n, 8, 9).second;
	//return 0;
	while (s.size() != 0) {
		ans *= 2;
		ans %= mod;
		queue<int> q;
		q.push(*s.begin());
		color[*s.begin()] = 1;
		while (!q.empty()) {
			int cur = q.front();
			q.pop();
			s.erase(cur);
			update_ends(0, 0, 2 * n, segments[cur].first, { -1, -1 });
			update_starts(0, 0, 2 * n, segments[cur].second, { 5 * MAXN, -1 });
			int f;
			while (true) {
				pair<int, int> g = query_ends(0, 0, 2 * n, segments[cur].first, segments[cur].second + 1);
				f = g.second;
				if (f == -1 || g.first < segments[cur].second)
					break;
				update_ends(0, 0, 2 * n, segments[f].first, {-1, -1});
				color[f] = -color[cur];
				q.push(f);
			}
			while (true) {
				/*if (cur == 4) {
					cout << "HERE\n";
				}*/
				pair<int, int> g = query_starts(0, 0, 2 * n, segments[cur].first, segments[cur].second + 1);
				f = g.second;
				if (f == -1 || g.first > segments[cur].first)
					break;
				update_starts(0, 0, 2 * n, segments[f].second, {5 * MAXN, -1});
				color[f] = -color[cur];
				q.push(f);
			}
		}
	}
	vector<int> v[2];
	for (auto act : actions) {
		if (act.type) {
			v[(color[act.id] + 1) / 2].push_back(act.id);
		}
		else {
			if (v[(color[act.id] + 1) / 2].back() != act.id) {
				cout << "0";
				return 0;
			}
			v[(color[act.id] + 1) / 2].pop_back();
		}
	}
	cout << ans;
	return 0;
}

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