Submission #874161

#	Time	Username	Problem	Language	Result	Execution time	Memory
874161		LucaLucaM	Passport (JOI23_passport)	C++17	22 / 100	2072 ms	21852 KiB

passport

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#warning That's the baby, that's not my baby

typedef long long ll;

/**

ce cred eu ca se intampla defapt e ca mereu voi putea accesa un interval de tari

si atunci o sa am o dinamica de genu

dp[i][l] =def= care e cel mai din dreapta r la care pot ajunge dupa i operatii, a.i. am capatul din stanga pe pozitia l

**/

struct Country {
  int l, r;
};

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

  int n;
  std::cin >> n;
  std::vector<Country> v(n + 1);
  int rMax[n + 1] = {};
  for (int i = 1; i <= n; i++) {
    std::cin >> v[i].l >> v[i].r;
    rMax[i] = std::max(rMax[i - 1], v[i].r);
  }
  int q;
  std::cin >> q;

  while (q--) {
    int x;
    std::cin >> x;
    if (x == 1) {
      int answer = 0;
      while (x != n && rMax[x] > x) {
        x = rMax[x];
        answer++;
      }
      if (x != n) {
        answer = -1;
      }
      std::cout << answer << '\n';
    } else {
      int dp[n + 2][n + 1];
      memset(dp, 0, sizeof(dp));
      dp[0][x] = x;
      for (int i = 0; i < n + 2; i++) {
        for (int l = 1; l <= n; l++) {
          for (int j = l; j <= dp[i][l]; j++) {
            int newL = std::min(l, v[j].l);
            dp[i + 1][newL] = std::max(dp[i + 1][newL], std::max(dp[i][l], v[j].r));
          }
        }
      }
      int answer = -1;
      for (int i = 0; i < n + 2 && answer == -1; i++) {
        if (dp[i][1] == n) {
          answer = i;
        }
      }
      std::cout << answer << '\n';
    }
  }

  return 0;
}

Compilation message (stderr)

passport.cpp:6:2: warning: #warning That's the baby, that's not my baby [-Wcpp]
    6 | #warning That's the baby, that's not my baby
      |  ^~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46