제출 #129166

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
129166		doowey	Long Mansion (JOI17_long_mansion)	C++14	5 / 100	251 ms	28376 KiB

long_mansion

#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 value[N * 4 + 512];

void modify(int node,int cl, int cr, int p, int v){
    if(cl == cr){
        value[node] = v;
        return;
    }
    int mid = (cl + cr) / 2;
    if(mid >= p)
        modify(node * 2, cl, mid, p, v);
    else
        modify(node * 2 + 1, mid + 1, cr, p, v);
    value[node] = min(value[node * 2], value[node * 2 + 1]);
}

int ask(int node, int cl, int cr, int x){
    if(cl == cr)
        return cl;
    int mid = (cl + cr) / 2;
    if(value[node * 2] < x)
        return ask(node * 2, cl, mid, x); 
    else
        return ask(node * 2 + 1, mid + 1, cr, x);
}

int fin(int node, int cl, int cr, int p){
    if(cl == cr){
        return value[node];
    }
    int mid = (cl + cr) / 2;
    if(mid >= p)
        return fin(node * 2, cl, mid, p);
    else
        return fin(node * 2 + 1, mid + 1, cr, p);
}

int gl[N];
int gr[N];
int req[N];
vector<int> col[N];
int las[N];
int lm[N];
int rm[N];

int m;


int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1; i < n; i ++ )
        cin >> req[i];
    int k, m;
    for(int i = 1; i <= n; i ++ ){
        cin >> k;
        for(int j = 0 ; j < k ; j ++ ){
            cin >> m;
            col[i].push_back(m);
        }
    }
    m = n + 1;
    for(int i = 1; i <= n; i ++ )
        las[i] = n + 1;
    for(int i = n ;i > 1; i -- ){
        for(auto p : col[i])
            las[p] = i;
        gl[i - 1] = las[req[i - 1]];
    }
    for(int i = 1; i <= n ; i ++ )
        las[i] = 0;
    for(int i = 1; i < n; i ++ ){
        for(auto p : col[i])
            las[p] = i;
        gr[i + 1] = las[req[i]];
    }
    modify(1, 1, m, 1, N);
    for(int i = 2; i <= n; i ++ )
        modify(1, 1, m, i, gr[i]);
    vector<int> id;
    rm[1] = ask(1, 1, m, 1) - 1;
    rm[1] = 1;
    lm[1] = 1;
    id.push_back(1);
    for(int i = 2 ; i <= n; i ++ ){
        lm[i] = i;
        rm[i] = i;
        modify(1, 1, m, i, N);
        while(1){
            rm[i] = ask(1, 1, m, lm[i]) - 1;
            if(lm[i] == 1 || gl[lm[i] - 1] > rm[i]) break;
            lm[i] = lm[lm[i] - 1];
        }
    }
    int q;
    cin >> q;
    int x, y;
    for(int i = 0 ; i < q; i ++ ){
        cin >> x >> y;
        if(y >= lm[x] && y <= rm[x])
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 15
• Subtask 4: 0 / 75