oj.uz

Submission #128368

# Submission time Handle Problem Language Result Execution time Memory
128368 2019-07-10T19:26:15 Z doowey Long Mansion (JOI17_long_mansion) C++14
0 / 100
 523 ms 20052 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)5e5 + 9;
int L[N];
int R[N];
int C[N];
vector<int> ls[N];

int las[N];
int lf[N];
int rf[N];


int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1; i < n; i ++ ){
        cin >> C[i];
    }
    int x, k;
    for(int i = 1; i <= n ; i ++ ){
        cin >> k;
        for(int j = 0 ; j < k ; j ++ ){
            cin >> x;
            ls[i].push_back(x);
        }
    }
    for(int j = 1; j <= n; j ++ )
        las[j] = -1;
    for(int i = 1; i < n; i ++ ){
        for(auto p : ls[i])
            las[p] = i;
        lf[i + 1] = las[C[i]];
    }
    for(int j = 1; j <= n; j ++ )
        las[j] = -1;
    for(int i = n; i > 1; i -- ){
        for(auto p : ls[i])
            las[p] = i;
        rf[i - 1] = las[C[i - 1]];
    }
    for(int i = 1; i <= n; i ++ ){
        L[i] = i;
        R[i] = i;
        while(1){
            if(L[i] != 1 && rf[L[i] - 1] <= R[i] && rf[L[i] - 1] != -1){
                L[i] = min(L[i], L[L[i]-1]);
                R[i] = max(R[i], R[L[i]-1]);
            }
            else if(R[i] != n && lf[R[i] + 1] >= L[i] && lf[R[i] + 1] != -1){
                R[i] ++ ;
            }
            else{
                break;
            }
        }
    }
    int Q;
    cin >> Q;
    int p, q;
    for(int i = 0 ; i < Q; i ++ ){
        cin >> p >> q;
        if(q >= L[p] && q <= R[p])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 12280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 12280 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 523 ms 20052 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 12280 KB Output isn't correct
2 Halted 0 ms 0 KB -