제출 #373084

#제출 시각아이디문제언어결과실행 시간메모리
373084casperwangPort Facility (JOI17_port_facility)C++14
0 / 100
1 ms364 KiB
#include <bits/stdc++.h>
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
 
const int MAXN = 1000000;
const int MOD = 1e9+7;
int n;
int s, t;
int arr[MAXN*2+1];
pii ord[MAXN+1];
deque <int> stk[2];
int cnt[MAXN+1];
int ans = 1;

signed main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> s >> t;
    arr[s] = arr[t] = i;
    ord[i].ff = s;
    ord[i].ss = t;
  }
  for (int i = 1; i <= 2*n; i++) {
    int id = arr[i];
    if (ord[id].ff == i) {
      bool flag = false;
      for (int j = 0; j < 2; j++) {
        if (!stk[j].size() || ord[stk[j].back()].ss > ord[id].ss) {
          stk[j].push_back(id);
          flag = true;
        }
      }
      if (!flag) {
        ans = ans * 2 % MOD;
        while (stk[0].size() && ord[stk[0].back()].ss < ord[id].ss)
          stk[0].pop_back();
        stk[0].push_back(id);
      }
    } else {
      for (int j = 0; j < 2; j++) {
        if (stk[j].size() && stk[j].back() == id) {
          cnt[id]++;
          stk[j].pop_back();
        }
      }
    }
  }
  for (int i = 1; i <= n; i++)
    ans = ans * cnt[i] % MOD;
  cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...