Submission #373084

#	Time	Username	Problem	Language	Result	Execution time	Memory
373084		casperwang	Port Facility (JOI17_port_facility)	C++14	0 / 100	1 ms	364 KiB

port_facility

#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';
}

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