Submission #972834

#	Time	Username	Problem	Language	Result	Execution time	Memory
972834		abczz	Port Facility (JOI17_port_facility)	C++14	100 / 100	2247 ms	975100 KiB

port_facility

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <map>
#define ll long long

using namespace std;

bool B[2000000];
vector <ll> V;
vector <array<ll, 2> > R, Q;
ll A[2000000], L[2000000], M = 1e9 + 7;
struct SegTree{
  vector <ll> st[8000000];
  vector <ll> st2[8000000];
  void build(ll id, ll l, ll r) {
    if (l == r) {
      if (A[l] != -1) st[id].push_back(A[l]);
      else st2[id].push_back(L[l]);
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    int i = 0, j = 0;
    while (i < st[id*2].size() && j < st[id*2+1].size()) {
      if (st[id*2][i] < st[id*2+1][j]) st[id].push_back(st[id*2][i++]);
      else st[id].push_back(st[id*2+1][j++]);
    }
    while (i < st[id*2].size()) st[id].push_back(st[id*2][i++]);
    while (j < st[id*2+1].size()) st[id].push_back(st[id*2+1][j++]);
    i = 0, j = 0;
    while (i < st2[id*2].size() && j < st2[id*2+1].size()) {
      if (st2[id*2][i] > st2[id*2+1][j]) st2[id].push_back(st2[id*2][i++]);
      else st2[id].push_back(st2[id*2+1][j++]);
    }
    while (i < st2[id*2].size()) st2[id].push_back(st2[id*2][i++]);
    while (j < st2[id*2+1].size()) st2[id].push_back(st2[id*2+1][j++]);
  }
  void query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      while (!st[id].empty()) {
        auto u = st[id].back();
        if (B[u] || qr < u) {
          if (!B[u]) {
            R.push_back({L[u], u});
            B[L[u]] = B[u] = 1;
          }
          st[id].pop_back();
        }
        else break;
      }
      while (!st2[id].empty()) {
        auto u = st2[id].back();
        if (B[u] || u < ql) {
          if (!B[u]) {
            R.push_back({u, A[u]});
            B[u] = B[A[u]] = 1;
          }
          st2[id].pop_back();
        }
        else break;
      }
      return;
    }
    ll mid = (l+r)/2;
    query(id*2, l, mid, ql, qr);
    query(id*2+1, mid+1, r, ql, qr);
  }
} ST;
ll n, a, b, f = 1;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n;
  for (int i=0; i<2*n; ++i) A[i] = L[i] = -1;
  for (int i=0; i<n; ++i) {
    cin >> a >> b;
    --a, --b;
    L[b] = a;
    A[a] = b;
  }
  ST.build(1, 0, 2*n-1);
  for (int i=0; i<2*n; ++i) {
    if (!B[i]) {
      f *= 2;
      f %= M;
      B[i] = B[A[i]] = 1;
      R.clear();
      Q.clear();
      Q.push_back({i, A[i]});
      while (true) {
        for (auto [l, r] : Q) {
          ST.query(1, 0, 2*n-1, l, r);
        }
        Q.clear();
        V.clear();
        if (R.empty()) break;
        sort(R.begin(), R.end());
        for (auto [x, y] : R) {
          while (!V.empty() && V.back() < x) {
            V.pop_back();
          }
          if (!V.empty() && V.back() < y) {
            cout << "0\n";
            return 0;
          }
          V.push_back(y);
        }
        swap(R, Q);
      }
    }
  }
  cout << f << '\n';
}

Compilation message (stderr)

port_facility.cpp: In member function 'void SegTree::build(long long int, long long int, long long int)':
port_facility.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while (i < st[id*2].size() && j < st[id*2+1].size()) {
      |            ~~^~~~~~~~~~~~~~~~~
port_facility.cpp:27:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     while (i < st[id*2].size() && j < st[id*2+1].size()) {
      |                                   ~~^~~~~~~~~~~~~~~~~~~
port_facility.cpp:31:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     while (i < st[id*2].size()) st[id].push_back(st[id*2][i++]);
      |            ~~^~~~~~~~~~~~~~~~~
port_facility.cpp:32:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     while (j < st[id*2+1].size()) st[id].push_back(st[id*2+1][j++]);
      |            ~~^~~~~~~~~~~~~~~~~~~
port_facility.cpp:34:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while (i < st2[id*2].size() && j < st2[id*2+1].size()) {
      |            ~~^~~~~~~~~~~~~~~~~~
port_facility.cpp:34:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while (i < st2[id*2].size() && j < st2[id*2+1].size()) {
      |                                    ~~^~~~~~~~~~~~~~~~~~~~
port_facility.cpp:38:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     while (i < st2[id*2].size()) st2[id].push_back(st2[id*2][i++]);
      |            ~~^~~~~~~~~~~~~~~~~~
port_facility.cpp:39:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     while (j < st2[id*2+1].size()) st2[id].push_back(st2[id*2+1][j++]);
      |            ~~^~~~~~~~~~~~~~~~~~~~
port_facility.cpp: In function 'int main()':
port_facility.cpp:95:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |         for (auto [l, r] : Q) {
      |                   ^
port_facility.cpp:102:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |         for (auto [x, y] : R) {
      |                   ^

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