Submission #984334

#	Time	Username	Problem	Language	Result	Execution time	Memory
984334		yellowtoad	Port Facility (JOI17_port_facility)	C++17	0 / 100	13 ms	49804 KiB

port_facility

#include <iostream>
#include <algorithm>
#include <vector>
#define f first
#define s second
#define int long long
using namespace std;
 
const int mod = 1e9+7;
int n, d[2000010], p[2000010], cnt, ans = 1;
bool hv;
pair<int,int> a[1000010];
vector<int> aa, bb, amin, bmin, v[2000010], tmp;
 
bool check(int i, int j) {
	if ((a[i].f < a[j].f) && (a[j].f < a[i].s) && (a[i].s < a[j].s)) return 1;
	swap(i,j);
	if ((a[i].f < a[j].f) && (a[j].f < a[i].s) && (a[i].s < a[j].s)) return 1;
	return 0;
}
 
int dsu(int u) {
	if (p[u] == u) return u;
	return p[u] = dsu(p[u]);
}
 
signed main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i].f >> a[i].s;
	sort(a+1,a+n+1);
	for (int i = 1; i <= n; i++) p[i] = i;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j < i; j++) {
			if (check(i,j)) p[dsu(i)] = p[dsu(j)];
		}
	}
	for (int i = 1; i <= n; i++) v[p[dsu(i)]].push_back(i);
	for (int i = 1; i <= n; i++) {
		for (int k = 0; k < v[i].size(); k++) {
			int j = v[i][k];
			while (aa.size() && (aa.back() < a[j].f)) {
				aa.pop_back();
				while (amin.size() && ((aa.empty()) || (amin.back() < aa.back()))) {
					tmp.push_back(amin.back());
					amin.pop_back();
				}
				while (tmp.size()) {
					aa.push_back(tmp.back());
					tmp.pop_back();
				}
			}
			if ((aa.empty()) || (aa.back() > a[j].s)) {
				aa.push_back(a[j].s);
			} else {
				if (amin.size() && (amin.back() < a[j].s)) {
					cout << 0 << endl;
					return 0;
				}
				amin.push_back(a[j].s);
			}
		}
		if (v[i].size()) cnt++;
	}
	for (int i = 1; i <= cnt; i++) (ans *= 2) %= mod;
	cout << ans << endl;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:39:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for (int k = 0; k < v[i].size(); k++) {
      |                   ~~^~~~~~~~~~~~~

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