Submission #328951

#	Time	Username	Problem	Language	Result	Execution time	Memory
328951		pit4h	Port Facility (JOI17_port_facility)	C++14	0 / 100	18 ms	31852 KiB

port_facility

#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#ifndef LOCAL 
#define cerr if(0)cerr
#endif
using namespace std;
using ll = long long;
using ld = long double;
using vi = vector<int>;
using pii = pair<int, int>;
const int N = 1e6+1;
const ll mod = 1e9+7;
int l[N], r[N], nr[2*N], col[N];
bool is[N];
ll ans=1;
priority_queue<pii> r_min[N];
bool collide(int i, int it) {
	while(r_min[it].size() && !is[r_min[it].top().nd]) {
		r_min[it].pop();
	}
	if(r_min[it].size() && -r_min[it].top().st < r[i]) return true;
	return false;
}
void add(int id, int it) {
	r_min[it].push(mp(-r[id], id));
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin>>n;
	for(int i=0; i<n; ++i) {
		cin>>l[i]>>r[i];
		nr[l[i]]=i;
		nr[r[i]]=i;
	}
	
	for(int i=1; i<=2*n; ++i) {
		if(!is[nr[i]]) {
			is[nr[i]] = 1;
			if(!collide(nr[i], 1)) {
				col[i] += 1;
			}
			if(!collide(nr[i], 2)) {
				col[i] += 2;
			}
			if(col[i]==0) {
				ans = 0;
				break;
			}
			if(col[i]==3) {
				ans *= 2LL;
				ans %= mod;
				add(nr[i], 1);
			}
			else {
				add(nr[i], col[i]);
			}
		}
		else {
			is[nr[i]] = 0;
		}
	}
	cout<<ans;
}

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