Submission #337280

#	Time	Username	Problem	Language	Result	Execution time	Memory
337280		super_j6	Port Facility (JOI17_port_facility)	C++14	0 / 100	1 ms	364 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 array<deque<int>, 2> T;

const int mod = 1000000007;
const int mxn = 1000001;
int n;
pi a[mxn];
stack<T> stk;

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;
	stk.push(T());
	for(int i = 0; i < 2; i++) stk.top()[i].push_front(2 * n + 2);
	for(int i = 0; i <= n; i++){
		while(1){
			for(int j = 0; j < 2; j++){
				while(stk.top()[j].front() < a[i].f) stk.top()[j].pop_front();
			}
			if(stk.top()[0].front() > stk.top()[1].front()){
				swap(stk.top()[0], stk.top()[1]);
			} 
			if(stk.top()[0].front() < 2 * n + 3) break;
			stk.pop(), (ret *= 2) %= mod;
		}
		if(a[i].s < stk.top()[0].front()){
			stk.push(T());
			for(int j = 0; j < 2; j++) stk.top()[j].push_front(2 * n + 3);
			stk.top()[0].push_front(a[i].s);
		}else if(stk.top()[1].front() == 2 * n + 3){
			T x;
			swap(stk.top(), x);
			stk.pop();
			if(a[i].s < stk.top()[0].front()){
				stk.push(T());
				swap(stk.top(), x);
				stk.top()[1].push_front(a[i].s);
			}else if(a[i].s < stk.top()[1].front()){
				x[0].pop_back();
				stk.top()[1].push_front(a[i].s);
				if(x[0].size() < stk.top()[0].size()){
					while(!x[0].empty()){
						stk.top()[0].push_front(x[0].back());
						x[0].pop_back();
					}
				}else{
					swap(x[0], stk.top()[0]);
					while(!x[0].empty()){
						stk.top()[0].push_back(x[0].front());
						x[0].pop_front();
					}
				}
			}else{
				ret = 0;
				break;
			}
		}else if(a[i].s < stk.top()[1].front()){
			stk.top()[1].push_front(a[i].s);
		}else{
			ret = 0;
			break;
		}
		for(int j = 0; j < 2; j++){
			for(int l = 1; l < stk.top()[j].size(); l++){
				if(stk.top()[j][l - 1] > stk.top()[j][l]){
					while(1) cout << 'f' << endl;
				}
			}
		}
	}
	
	cout << ret << endl;

	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:85:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |    for(int l = 1; l < stk.top()[j].size(); l++){
      |                   ~~^~~~~~~~~~~~~~~~~~~~~

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