제출 #1195677

#제출 시각아이디문제언어결과실행 시간메모리
1195677NAMINPort Facility (JOI17_port_facility)C++20
10 / 100
6095 ms8132 KiB
#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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...