제출 #1195677

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1195677		NAMIN	Port Facility (JOI17_port_facility)	C++20	10 / 100	6095 ms	8132 KiB

port_facility

#include <bits/stdc++.h>

#define endl "\n"
#define ll long long

using namespace std;

const int MOD = 1e9+7;
int N;
vector<pair<int,int>> seg;

ll calc(int cur,vector<int> A,vector<int> B){
	if(cur==N){
		return 1;
	}
	
	while(A.size() > 0 && A.back() <= seg[cur].first)
		A.pop_back();
	while(B.size() > 0 && B.back() <= seg[cur].first)
		B.pop_back();

	ll res = 0;
	if(A.size() == 0 || A.back() >= seg[cur].second){
		A.push_back(seg[cur].second);
		(res += calc(cur+1,A,B))%=MOD;
		A.pop_back();
	}
	if(B.size() == 0 || B.back() >= seg[cur].second){
		B.push_back(seg[cur].second);
		(res += calc(cur+1,A,B))%=MOD;
		B.pop_back();
	}
	return res;
}

void solve(){
	cin >> N;
	seg.resize(N);
	for(int i=0;i<N;i++){
		cin >> seg[i].first >> seg[i].second;
	}
	sort(seg.begin(),seg.end());
	
	cout << calc(0,{},{}) << endl;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	//cin >> t;
 	while(t--){
		solve();
	}
	return 0;
}

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