oj.uz

답안 #684321

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684321 2023-01-20T22:04:49 Z stevancv Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 19332 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

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 10 ms 12244 KB Output is correct
3 Correct 22 ms 12372 KB Output is correct
4 Correct 8 ms 12120 KB Output is correct
5 Correct 8 ms 12148 KB Output is correct
6 Correct 10 ms 12244 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 10 ms 12244 KB Output is correct
3 Correct 22 ms 12372 KB Output is correct
4 Correct 8 ms 12120 KB Output is correct
5 Correct 8 ms 12148 KB Output is correct
6 Correct 10 ms 12244 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 96 ms 13696 KB Output is correct
9 Correct 96 ms 13704 KB Output is correct
10 Correct 98 ms 13872 KB Output is correct
11 Correct 105 ms 14156 KB Output is correct
12 Correct 108 ms 13856 KB Output is correct
13 Correct 94 ms 14028 KB Output is correct
14 Correct 96 ms 13892 KB Output is correct
15 Correct 101 ms 13944 KB Output is correct
16 Correct 93 ms 14140 KB Output is correct
17 Correct 93 ms 13912 KB Output is correct
18 Correct 93 ms 13916 KB Output is correct
19 Correct 94 ms 13864 KB Output is correct
20 Correct 91 ms 14064 KB Output is correct
21 Correct 94 ms 14156 KB Output is correct
22 Correct 97 ms 13876 KB Output is correct
23 Correct 114 ms 13836 KB Output is correct
24 Correct 101 ms 13836 KB Output is correct
25 Correct 95 ms 13776 KB Output is correct
26 Correct 108 ms 13660 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 723 ms 19308 KB Output is correct
2 Correct 1525 ms 19332 KB Output is correct
3 Correct 2930 ms 19260 KB Output is correct
4 Correct 978 ms 19252 KB Output is correct
5 Correct 1127 ms 19304 KB Output is correct
6 Execution timed out 3068 ms 18576 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 12244 KB Output is correct
2 Correct 10 ms 12244 KB Output is correct
3 Correct 22 ms 12372 KB Output is correct
4 Correct 8 ms 12120 KB Output is correct
5 Correct 8 ms 12148 KB Output is correct
6 Correct 10 ms 12244 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 96 ms 13696 KB Output is correct
9 Correct 96 ms 13704 KB Output is correct
10 Correct 98 ms 13872 KB Output is correct
11 Correct 105 ms 14156 KB Output is correct
12 Correct 108 ms 13856 KB Output is correct
13 Correct 94 ms 14028 KB Output is correct
14 Correct 96 ms 13892 KB Output is correct
15 Correct 101 ms 13944 KB Output is correct
16 Correct 93 ms 14140 KB Output is correct
17 Correct 93 ms 13912 KB Output is correct
18 Correct 93 ms 13916 KB Output is correct
19 Correct 94 ms 13864 KB Output is correct
20 Correct 91 ms 14064 KB Output is correct
21 Correct 94 ms 14156 KB Output is correct
22 Correct 97 ms 13876 KB Output is correct
23 Correct 114 ms 13836 KB Output is correct
24 Correct 101 ms 13836 KB Output is correct
25 Correct 95 ms 13776 KB Output is correct
26 Correct 108 ms 13660 KB Output is correct
27 Correct 723 ms 19308 KB Output is correct
28 Correct 1525 ms 19332 KB Output is correct
29 Correct 2930 ms 19260 KB Output is correct
30 Correct 978 ms 19252 KB Output is correct
31 Correct 1127 ms 19304 KB Output is correct
32 Execution timed out 3068 ms 18576 KB Time limit exceeded
33 Halted 0 ms 0 KB -