oj.uz

Submission #1065793

# Submission time Handle Problem Language Result Execution time Memory
1065793 2024-08-19T11:47:47 Z Unforgettablepl Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 11600 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> C(N+1);
    for(int i=1;i<N;i++)cin>>C[i];
    vector<vector<int>> keys(N+1);
    for(int i=1;i<=N;i++) {
        int b;cin>>b;
        keys[i].resize(b);
        for(int&j:keys[i])cin>>j;
    }
    vector<int> Lbound(N+1);
    vector<int> Rbound(N+1);
    for(int i=1;i<=N;i++) {
        int L = i;
        int R = i;
        vector<bool> have_key(N+1);
        for(int&x:keys[R])have_key[x]=true;
        while(true) {
            if(R!=N and have_key[C[R]]) {
                R++;
                for(int&x:keys[R])have_key[x]=true;
            } else if(L!=1 and have_key[C[L-1]]) {
                L--;
                for(int&x:keys[L])have_key[x]=true;
            } else break;
        }
        Lbound[i]=L;
        Rbound[i]=R;
    }
    int Q;
    cin >> Q;
    for(int i=1;i<=Q;i++) {
        int X,Y;cin>>X>>Y;
        if(Lbound[X]<=Y and Y<=Rbound[X])cout<<"YES\n";
        else cout << "NO\n";
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 8 ms 724 KB Output is correct
3 Correct 33 ms 916 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 13 ms 672 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 4 ms 604 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 8 ms 724 KB Output is correct
3 Correct 33 ms 916 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 13 ms 672 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 56 ms 6484 KB Output is correct
9 Correct 95 ms 6424 KB Output is correct
10 Correct 88 ms 6864 KB Output is correct
11 Correct 89 ms 7240 KB Output is correct
12 Correct 82 ms 5972 KB Output is correct
13 Correct 54 ms 6484 KB Output is correct
14 Correct 75 ms 6484 KB Output is correct
15 Correct 56 ms 6688 KB Output is correct
16 Correct 101 ms 6480 KB Output is correct
17 Correct 51 ms 6484 KB Output is correct
18 Correct 54 ms 6572 KB Output is correct
19 Correct 53 ms 6596 KB Output is correct
20 Correct 61 ms 6604 KB Output is correct
21 Correct 69 ms 6356 KB Output is correct
22 Correct 62 ms 6360 KB Output is correct
23 Correct 108 ms 6412 KB Output is correct
24 Correct 57 ms 6360 KB Output is correct
25 Correct 64 ms 6308 KB Output is correct
26 Correct 55 ms 6484 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3038 ms 11600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 8 ms 724 KB Output is correct
3 Correct 33 ms 916 KB Output is correct
4 Correct 2 ms 604 KB Output is correct
5 Correct 13 ms 672 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 56 ms 6484 KB Output is correct
9 Correct 95 ms 6424 KB Output is correct
10 Correct 88 ms 6864 KB Output is correct
11 Correct 89 ms 7240 KB Output is correct
12 Correct 82 ms 5972 KB Output is correct
13 Correct 54 ms 6484 KB Output is correct
14 Correct 75 ms 6484 KB Output is correct
15 Correct 56 ms 6688 KB Output is correct
16 Correct 101 ms 6480 KB Output is correct
17 Correct 51 ms 6484 KB Output is correct
18 Correct 54 ms 6572 KB Output is correct
19 Correct 53 ms 6596 KB Output is correct
20 Correct 61 ms 6604 KB Output is correct
21 Correct 69 ms 6356 KB Output is correct
22 Correct 62 ms 6360 KB Output is correct
23 Correct 108 ms 6412 KB Output is correct
24 Correct 57 ms 6360 KB Output is correct
25 Correct 64 ms 6308 KB Output is correct
26 Correct 55 ms 6484 KB Output is correct
27 Execution timed out 3038 ms 11600 KB Time limit exceeded
28 Halted 0 ms 0 KB -