Submission #94588

#	Time	Username	Problem	Language	Result	Execution time	Memory
94588		MB81	Port Facility (JOI17_port_facility)	C++11	0 / 100	2 ms	480 KiB

port_facility

// :)
// "Khodaya, be man "Tagwaye setiz" biamooz ta
//  dar anbuh masuliat nalaghzam ..." -Shariati
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define F first
#define S second
#define MP make_pair
using namespace std;
using namespace __gnu_pbds;
template <typename T> using ordered_set =  tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> using ordered_multiset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int64;
typedef pair<int,int> pii;
typedef pair<int64,int64> pii64;
const int maxn = 2e6+9;
const int64 M = 1e9+7;
const int64 I = 1e9;

vector <pii> v1;
int fen[2][maxn];

int n, ans = 1;

void upd (int x, int val, int id) {
	for (; x < maxn; x += x&-x)
		fen[id][x] += val;
	return;
}

int get (int x, int id) {
	int res = 0;
	for (; x; x -= x&-x)
		res += fen[id][x];
	return res;
}

int main () {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) {
		int st, en;
		cin >> st >> en;
		v1.push_back( MP( en, st ) );
	}
	sort(v1.begin(), v1.end());
	for (int i = 0; i < n; i++) {
		int x = v1[i].S, y = v1[i].F;
		int cur1 = get(x, 0);
		int cur2 = get(x, 1);
		if (cur1 + cur2 == 0) {
			ans = 2LL * ans % M;
			upd(x, 1, 0);
			upd(y + 1, -1, 0);
			continue;
		}
		if (cur1 > 0 && cur2 > 0)
			ans = 0;
		if (cur1 > 0) {
			upd(x, 1, 1);
			upd(y + 1, -1, 1);
		} else {
			upd(x, 1, 0);
			upd(y + 1, -1, 0);
		}
	}
	cout << ans << "\n";
}

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