oj.uz

Submission #684320

# Submission time Handle Problem Language Result Execution time Memory
684320 2023-01-20T22:03:50 Z stevancv Long Mansion (JOI17_long_mansion) C++11
10 / 100
 3000 ms 19424 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e5 + 2;
const int inf = 1e9;
int c[N], le[N], ri[N], l[N], r[N], lst[N];
vector<int> b[N];
bool Between(int L, int R, int x) {
    return L <= x && x <= R;
}
bool Can(int L, int R, int x) {
    return Between(L, R, le[x]) || Between(L, R, ri[x]);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i < n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) {
        int sz; cin >> sz;
        b[i].resize(sz);
        for (int j = 0; j < sz; j++) cin >> b[i][j];
    }
    for (int i = 1; i < n; i++) {
        for (int j : b[i]) lst[j] = i;
        le[i] = lst[c[i]];
    }
    for (int i = 1; i <= n; i++) lst[i] = 0;
    for (int i = n; i > 1; i--) {
        for (int j : b[i]) lst[j] = i;
        ri[i - 1] = lst[c[i - 1]];
    }
    for (int i = 1; i <= n; i++) {
        l[i] = r[i] = i;
        while (1) {
            if (l[i] > 1 && Can(l[i], r[i], l[i] - 1)) {
                l[i] = l[l[i] - 1];
                smax(r[i], r[l[i]]);
            }
            else if (r[i] < n && Can(l[i], r[i], r[i])) r[i]++;
            else break;
        }
    }
    int q; cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (Between(l[x], r[x], y)) cout << "YES" << en;
        else cout << "NO" << en;
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12240 KB Output is correct
2 Correct 10 ms 12244 KB Output is correct
3 Correct 21 ms 12380 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 10 ms 12244 KB Output is correct
6 Correct 8 ms 12236 KB Output is correct
7 Correct 9 ms 12232 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12240 KB Output is correct
2 Correct 10 ms 12244 KB Output is correct
3 Correct 21 ms 12380 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 10 ms 12244 KB Output is correct
6 Correct 8 ms 12236 KB Output is correct
7 Correct 9 ms 12232 KB Output is correct
8 Correct 98 ms 13688 KB Output is correct
9 Correct 97 ms 13772 KB Output is correct
10 Correct 105 ms 13916 KB Output is correct
11 Correct 105 ms 14132 KB Output is correct
12 Correct 89 ms 13896 KB Output is correct
13 Correct 94 ms 13900 KB Output is correct
14 Correct 90 ms 13900 KB Output is correct
15 Correct 101 ms 13992 KB Output is correct
16 Correct 92 ms 14204 KB Output is correct
17 Correct 90 ms 13880 KB Output is correct
18 Correct 107 ms 13900 KB Output is correct
19 Correct 94 ms 13940 KB Output is correct
20 Correct 93 ms 14096 KB Output is correct
21 Correct 97 ms 14140 KB Output is correct
22 Correct 96 ms 14088 KB Output is correct
23 Correct 120 ms 13804 KB Output is correct
24 Correct 102 ms 13764 KB Output is correct
25 Correct 110 ms 13708 KB Output is correct
26 Correct 94 ms 13756 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 19276 KB Output is correct
2 Correct 1475 ms 19344 KB Output is correct
3 Correct 2906 ms 19276 KB Output is correct
4 Correct 946 ms 19404 KB Output is correct
5 Correct 1082 ms 19372 KB Output is correct
6 Execution timed out 3053 ms 19424 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12240 KB Output is correct
2 Correct 10 ms 12244 KB Output is correct
3 Correct 21 ms 12380 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 10 ms 12244 KB Output is correct
6 Correct 8 ms 12236 KB Output is correct
7 Correct 9 ms 12232 KB Output is correct
8 Correct 98 ms 13688 KB Output is correct
9 Correct 97 ms 13772 KB Output is correct
10 Correct 105 ms 13916 KB Output is correct
11 Correct 105 ms 14132 KB Output is correct
12 Correct 89 ms 13896 KB Output is correct
13 Correct 94 ms 13900 KB Output is correct
14 Correct 90 ms 13900 KB Output is correct
15 Correct 101 ms 13992 KB Output is correct
16 Correct 92 ms 14204 KB Output is correct
17 Correct 90 ms 13880 KB Output is correct
18 Correct 107 ms 13900 KB Output is correct
19 Correct 94 ms 13940 KB Output is correct
20 Correct 93 ms 14096 KB Output is correct
21 Correct 97 ms 14140 KB Output is correct
22 Correct 96 ms 14088 KB Output is correct
23 Correct 120 ms 13804 KB Output is correct
24 Correct 102 ms 13764 KB Output is correct
25 Correct 110 ms 13708 KB Output is correct
26 Correct 94 ms 13756 KB Output is correct
27 Correct 759 ms 19276 KB Output is correct
28 Correct 1475 ms 19344 KB Output is correct
29 Correct 2906 ms 19276 KB Output is correct
30 Correct 946 ms 19404 KB Output is correct
31 Correct 1082 ms 19372 KB Output is correct
32 Execution timed out 3053 ms 19424 KB Time limit exceeded
33 Halted 0 ms 0 KB -