oj.uz

Submission #874161

# Submission time Handle Problem Language Result Execution time Memory
874161 2023-11-16T11:29:27 Z LucaLucaM Passport (JOI23_passport) C++17
22 / 100
 2000 ms 21852 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 25 ms 5052 KB Output is correct
5 Correct 24 ms 5204 KB Output is correct
6 Correct 27 ms 5216 KB Output is correct
7 Correct 20 ms 4440 KB Output is correct
8 Correct 18 ms 3676 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 456 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 9 ms 712 KB Output is correct
13 Correct 14 ms 600 KB Output is correct
14 Correct 14 ms 604 KB Output is correct
15 Correct 8 ms 604 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 456 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 9 ms 712 KB Output is correct
13 Correct 14 ms 600 KB Output is correct
14 Correct 14 ms 604 KB Output is correct
15 Correct 8 ms 604 KB Output is correct
16 Execution timed out 2072 ms 21852 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 456 KB Output is correct
11 Correct 6 ms 600 KB Output is correct
12 Correct 9 ms 712 KB Output is correct
13 Correct 14 ms 600 KB Output is correct
14 Correct 14 ms 604 KB Output is correct
15 Correct 8 ms 604 KB Output is correct
16 Execution timed out 2072 ms 21852 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 25 ms 5052 KB Output is correct
5 Correct 24 ms 5204 KB Output is correct
6 Correct 27 ms 5216 KB Output is correct
7 Correct 20 ms 4440 KB Output is correct
8 Correct 18 ms 3676 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 456 KB Output is correct
19 Correct 6 ms 600 KB Output is correct
20 Correct 9 ms 712 KB Output is correct
21 Correct 14 ms 600 KB Output is correct
22 Correct 14 ms 604 KB Output is correct
23 Correct 8 ms 604 KB Output is correct
24 Execution timed out 2072 ms 21852 KB Time limit exceeded
25 Halted 0 ms 0 KB -