oj.uz

Submission #766843

# Submission time Handle Problem Language Result Execution time Memory
766843 2023-06-26T08:08:22 Z dimash241 Passport (JOI23_passport) C++17
0 / 100
 95 ms 111808 KB 
#include <cstdio>
#include <random>
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <chrono>


#define ll long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
using namespace std;

// вправо, вниз, влево, вверх
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

// ход конем
//int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
//int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};

mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::system_clock::now().time_since_epoch().count());
int rndInteger (int l, int r) {
    return uniform_int_distribution<int> (l, r)(rnd);
}

const int MOD = (int) 998244353;
const int N = (int) 3000+7;

int n, q;
int L[N], R[N];
int ans[N], x[N];
int dp[N][N];
int minL[N][N], maxR[N][N];

int solve(int l, int r) {
    if(l == 1 && r == n) {
        return 1;
    }
    int &res = dp[l][r];
    if(res != -1) return res;
    res = 1e9;

    for (int p : {minL[l][r], maxR[l][r]}) {
        int nl = min(l, L[p]);
        int nr = max(r, R[p]);

        if(nl != l || nr != r) {
            res = min(res, solve(nl, nr) + 1);
        }
    }

    return res;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> L[i] >> R[i];

    for (int i = 1; i <= n; ++i) {
        minL[i][i] = i;
        maxR[i][i] = i;
        for (int j = i + 1; j <= n; ++j) {
            minL[i][j] = (L[j] > L[minL[i][j-1]] ? L[minL[i][j-1]] : j);
            maxR[i][j] = (R[j] > R[maxR[i][j-1]] ? j : maxR[i][j-1]);
        }
    }

    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> x[i];
        memset(dp, -1, sizeof dp);
        int res = solve(L[x[i]], R[x[i]]);
        if(res > n) res = -1;
        cout << res << '\n';
    }

    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 35664 KB Output is correct
2 Correct 13 ms 35660 KB Output is correct
3 Correct 14 ms 35668 KB Output is correct
4 Runtime error 95 ms 111808 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 35748 KB Output is correct
2 Correct 14 ms 35716 KB Output is correct
3 Correct 14 ms 35648 KB Output is correct
4 Correct 13 ms 35656 KB Output is correct
5 Correct 13 ms 35672 KB Output is correct
6 Correct 14 ms 35656 KB Output is correct
7 Correct 14 ms 35668 KB Output is correct
8 Correct 13 ms 35708 KB Output is correct
9 Correct 14 ms 35736 KB Output is correct
10 Correct 14 ms 35760 KB Output is correct
11 Correct 16 ms 38236 KB Output is correct
12 Incorrect 18 ms 38448 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 35748 KB Output is correct
2 Correct 14 ms 35716 KB Output is correct
3 Correct 14 ms 35648 KB Output is correct
4 Correct 13 ms 35656 KB Output is correct
5 Correct 13 ms 35672 KB Output is correct
6 Correct 14 ms 35656 KB Output is correct
7 Correct 14 ms 35668 KB Output is correct
8 Correct 13 ms 35708 KB Output is correct
9 Correct 14 ms 35736 KB Output is correct
10 Correct 14 ms 35760 KB Output is correct
11 Correct 16 ms 38236 KB Output is correct
12 Incorrect 18 ms 38448 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 35748 KB Output is correct
2 Correct 14 ms 35716 KB Output is correct
3 Correct 14 ms 35648 KB Output is correct
4 Correct 13 ms 35656 KB Output is correct
5 Correct 13 ms 35672 KB Output is correct
6 Correct 14 ms 35656 KB Output is correct
7 Correct 14 ms 35668 KB Output is correct
8 Correct 13 ms 35708 KB Output is correct
9 Correct 14 ms 35736 KB Output is correct
10 Correct 14 ms 35760 KB Output is correct
11 Correct 16 ms 38236 KB Output is correct
12 Incorrect 18 ms 38448 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 35664 KB Output is correct
2 Correct 13 ms 35660 KB Output is correct
3 Correct 14 ms 35668 KB Output is correct
4 Runtime error 95 ms 111808 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -