oj.uz

Submission #950492

# Submission time Handle Problem Language Result Execution time Memory
950492 2024-03-20T11:07:42 Z LucaLucaM Port Facility (JOI17_port_facility) C++17
0 / 100
 1 ms 2392 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2392 KB Output isn't correct
2 Halted 0 ms 0 KB -