oj.uz

Submission #1101852

# Submission time Handle Problem Language Result Execution time Memory
1101852 2024-10-17T03:43:46 Z irmuun Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 12376 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n;
    cin>>n;
    ll c[n+5];
    for(ll i=1;i<n;i++){
        cin>>c[i];
    }
    ll b[n+5];
    vector<vector<ll>>key(n+5);
    for(ll i=1;i<=n;i++){
        cin>>b[i];
        key[i].resize(b[i]);
        for(ll j=0;j<b[i];j++){
            cin>>key[i][j];
        }
    }
    vector<bool>have(n+1,0);
    auto add=[&](ll x) ->void{
        for(ll k:key[x]){
            have[k]=true;
        }
    };
    ll L[n+5],R[n+5];
    for(ll i=1;i<=n;i++){
        ll l=i,r=i;
        fill(all(have),0);
        add(i);
        while(l>1||r<n){
            if(l>1&&have[c[l-1]]){
                l--;
                add(l);
            }
            else if(r<n&&have[c[r]]){
                r++;
                add(r);
            }
            else{
                break;
            }
        }
        L[i]=l;
        R[i]=r;
    }
    ll q;
    cin>>q;
    while(q--){
        ll x,y;
        cin>>x>>y;
        if(L[x]<=y&&y<=R[x]){
            cout<<"YES\n";
        }
        else{
            cout<<"NO\n";
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 14 ms 776 KB Output is correct
3 Correct 41 ms 960 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Correct 14 ms 688 KB Output is correct
6 Correct 6 ms 704 KB Output is correct
7 Correct 6 ms 596 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 14 ms 776 KB Output is correct
3 Correct 41 ms 960 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Correct 14 ms 688 KB Output is correct
6 Correct 6 ms 704 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 72 ms 6332 KB Output is correct
9 Correct 62 ms 6484 KB Output is correct
10 Correct 76 ms 6708 KB Output is correct
11 Correct 100 ms 7244 KB Output is correct
12 Correct 55 ms 5972 KB Output is correct
13 Correct 59 ms 6732 KB Output is correct
14 Correct 66 ms 6732 KB Output is correct
15 Correct 77 ms 6528 KB Output is correct
16 Correct 68 ms 6360 KB Output is correct
17 Correct 58 ms 6476 KB Output is correct
18 Correct 61 ms 6732 KB Output is correct
19 Correct 60 ms 6548 KB Output is correct
20 Correct 67 ms 6476 KB Output is correct
21 Correct 63 ms 6360 KB Output is correct
22 Correct 59 ms 6476 KB Output is correct
23 Correct 61 ms 6488 KB Output is correct
24 Correct 67 ms 6384 KB Output is correct
25 Correct 66 ms 6416 KB Output is correct
26 Correct 65 ms 6496 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 596 KB Output is correct
2 Correct 14 ms 776 KB Output is correct
3 Correct 41 ms 960 KB Output is correct
4 Correct 4 ms 632 KB Output is correct
5 Correct 14 ms 688 KB Output is correct
6 Correct 6 ms 704 KB Output is correct
7 Correct 6 ms 596 KB Output is correct
8 Correct 72 ms 6332 KB Output is correct
9 Correct 62 ms 6484 KB Output is correct
10 Correct 76 ms 6708 KB Output is correct
11 Correct 100 ms 7244 KB Output is correct
12 Correct 55 ms 5972 KB Output is correct
13 Correct 59 ms 6732 KB Output is correct
14 Correct 66 ms 6732 KB Output is correct
15 Correct 77 ms 6528 KB Output is correct
16 Correct 68 ms 6360 KB Output is correct
17 Correct 58 ms 6476 KB Output is correct
18 Correct 61 ms 6732 KB Output is correct
19 Correct 60 ms 6548 KB Output is correct
20 Correct 67 ms 6476 KB Output is correct
21 Correct 63 ms 6360 KB Output is correct
22 Correct 59 ms 6476 KB Output is correct
23 Correct 61 ms 6488 KB Output is correct
24 Correct 67 ms 6384 KB Output is correct
25 Correct 66 ms 6416 KB Output is correct
26 Correct 65 ms 6496 KB Output is correct
27 Execution timed out 3046 ms 12376 KB Time limit exceeded
28 Halted 0 ms 0 KB -