Submission #42921

#	Time	Username	Problem	Language	Result	Execution time	Memory
42921		almasalmas	Port Facility (JOI17_port_facility)	C++14	0 / 100	1 ms	376 KiB

port_facility

#include <bits/stdc++.h>

#define int long long 

using namespace std;

int mod = 1e9 + 7;
pair <int, int> asd[1000001];
int a[1000001];
int b[1000001];
int t1[4000001];
int t2[4000001];
int ans = 1, id;
int n;

void upd (int pos, int val, int v = 1, int tl = 1, int tr = n + n) {
	if (tl == tr) {
		t1[v] = val;
		t2[v] = val;
		return;
	}
	int tm = (tl + tr) / 2;
	if (tm >= pos) {
		upd (pos, val, v + v, tl, tm);
	}
	else upd (pos, val, v + v + 1, tm + 1, tr);
	t1[v] = min (t1[v + v], t1[v + v + 1]);
	t2[v] = max (t2[v + v], t2[v + v + 1]);
}

pair <int, int> get (int l, int r, int v = 1, int tl = 1, int tr = n + n) {
	if (tr < l || tl > r) return make_pair (10, -10);
	if (tl >= l && tr <= r) return make_pair (t1[v], t2[v]);
	int tm = (tl + tr) / 2;
	pair <int, int> x = get (l, r, v + v, tl, tm);
	pair <int, int> y = get (l, r, v + v + 1, tm + 1, tr);
	x.first = min (x.first, y.first);
	x.second = max (x.second, y.second);
	return x;
}

 main () {
 	ios_base::sync_with_stdio (0);
 	cin.tie (0), cout.tie (0);
 	cin >> n;
	for (int i = 1;i <= n;i ++) {
		cin >> asd[i].first >> asd[i].second;
	}
	sort (asd + 1, asd + n + 1);
	for (int i = 1;i <= n;i ++) {
		a[i] = asd[i].first;
		b[i] = asd[i].second;
	}
	for (int i = 1;i <= n;i ++) {
		int mn = get (a[i], b[i]).first;
		int mx = get (a[i], b[i]).second;
	//	cout << mn << ' ' << mx << endl;
		if (mn == -1 && mx == 2) {
			cout << 0;
			return 0;
		}    
		int val = -1;
		if (mn == -1) val = 2;
		else if (mx == 2) val = -1;
		else ans = (ans + ans) % mod;	
		upd (b[i], val); 
	}
	cout << ans;
	return 0;
}

Compilation message (stderr)

port_facility.cpp:42:8: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  main () {
        ^

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