Submission #337294

#	Time	Username	Problem	Language	Result	Execution time	Memory
337294		super_j6	Port Facility (JOI17_port_facility)	C++14	78 / 100	990 ms	1048580 KiB

port_facility

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <array>
#include <stack>
#include <deque>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second
 
typedef pair<deque<int>, deque<int>> T;
 
const int mod = 1000000007;
const int mxn = 1000001;
int n;
pi a[mxn];
stack<T> stk;
 
int f(int x){
	if(!x) return stk.top().f.empty() ? 2 * n + 2 : stk.top().f.front();
	else return stk.top().s.empty() ? 2 * n + 2 : stk.top().s.front();
}
 
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	
	for(int i = 0; i < n; i++) cin >> a[i].f >> a[i].s;
	a[n] = {2 * n + 1, 2 * n + 1};
	
	sort(a, a + n);
	
	int ret = 1;
	for(int i = 0; i <= n; i++){
		while(!stk.empty()){
			for(int j = 0; j < 2; j++){
				while(f(j) < a[i].f){
					if(!j) stk.top().f.pop_front();
					else stk.top().s.pop_front();
				} 
			}
			if(f(0) > f(1)) swap(stk.top().f, stk.top().s);
			if(!stk.top().f.empty()) break;
			stk.pop(), (ret *= 2) %= mod;
		}
		if(stk.empty() || a[i].s < f(0)){
			stk.push(T());
			stk.top().f.push_front(a[i].s);
		}else{
			while(stk.size() > 1 && stk.top().s.empty()){
				T x;
				swap(stk.top(), x);
				stk.pop();
				if(a[i].s < f(0)){
					stk.push(T());
					swap(stk.top(), x);
					break;
				}
				if(x.f.size() < stk.top().f.size()){
					while(!x.f.empty()){
						stk.top().f.push_front(x.f.back());
						x.f.pop_back();
					}
				}else{
					swap(x.f, stk.top().f);
					while(!x.f.empty()){
						stk.top().f.push_back(x.f.front());
						x.f.pop_front();
					}
				}
			}
			if(a[i].s > f(1)){
				ret = 0;
				break;
			}
			stk.top().s.push_front(a[i].s);
		}
	}
	
	cout << ret << endl;
 
	return 0;
}

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