Submission #950492

#	Time	Username	Problem	Language	Result	Execution time	Memory
950492		LucaLucaM	Port Facility (JOI17_port_facility)	C++17	0 / 100	1 ms	2392 KiB

port_facility

#include <iostream>
#include <cassert>
#include <algorithm>
#include <vector>
#include <cstring>
#include <set>

typedef long long ll;

const int NMAX = 1e6;
const int mod = 1e9 + 7;

int p[2 * NMAX + 1];
int add[2 * NMAX + 1];

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

  int n;
  std::cin >> n;

  for (int i = 1; i <= n; i++) {
    int a, b;
    std::cin >> a >> b;
    p[a] = b;
  }

  /**

12345678
XYXZYTTZ

cum verific daca pot in 1 mod?
cum verifica daca pot in 2 moduri?


[    ]
  [    ]
    [   ]

cum verific sa nu am i < j < k si a[k] < b[i] < b[j] < b[k]?

  **/

  int where = 2;

  int a[n], b[n];
  for (int i = 1, k = 0; i <= 2 * n; i++) {
    if (!p[i]) {
      continue;
    }
    a[k] = i;
    b[k] = p[i];
    k++;
  }

  assert(std::is_sorted(a, a + n));

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        if (a[i] < a[j] && a[j] < a[k] && a[i] < b[j] && b[j] < b[k] && b[k] < b[i]) {
          std::cout << 0;
          return 0;
        }
      }
    }
  }

  std::set<int> st;
  int answer = 1;

  for (int i = 1; i <= 2 * n; i++) {
    if (!p[i]) {
      continue;
    }
    while (!st.empty() && *st.begin() < i) {
      st.erase(st.begin());
    }
    if (st.empty() || *st.begin() > p[i]) {
      answer = answer * 2 % mod;
    }
    st.insert(p[i]);
  }

  std::cout << answer;

  return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:46:7: warning: unused variable 'where' [-Wunused-variable]
   46 |   int where = 2;
      |       ^~~~~

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