Submission #957601

#	Time	Username	Problem	Language	Result	Execution time	Memory
957601		parlimoos	Long Mansion (JOI17_long_mansion)	C++14	25 / 100	2432 ms	50548 KiB

long_mansion

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n , q , in[500000][2];
vector<int> inxs[500000];
int seg[2000001][2] , seginf[2000001][2];

void init(){
    for(int i = 0 ; i < n ; i++){
        if(in[i][0] != -1){
            auto itr = lb(inxs[in[i][0]].bg() , inxs[in[i][0]].end() , i);
            if(itr == inxs[in[i][0]].bg()) in[i][0] = -1;
            else in[i][0] = *(--itr);
        }
        if(in[i][1] != -1){
            auto itr = ub(inxs[in[i][1]].bg() , inxs[in[i][1]].end() , i);
            if(itr == inxs[in[i][1]].end()) in[i][1] = n;
            else in[i][1] = *(itr);
        }
    }
}
void buildSeg(int l = 0 , int r = n - 1 , int i = 1){
    seginf[i][0] = l , seginf[i][1] = r;
    if(l == r){
        seg[i][0] = in[l][0];
        seg[i][1] = in[l][1];
    }else{
        int c = (r + l - 1) >> 1;
        buildSeg(l , c , i << 1) , buildSeg(c + 1 , r , (i << 1) | 1);
        seg[i][0] = min(seg[i << 1][0] , seg[(i << 1) | 1][0]);
        seg[i][1] = max(seg[i << 1][1] , seg[(i << 1) | 1][1]);
    }
}
int getSeg(int l , int r , int i , int md){
    if(seginf[i][0] >= l and seginf[i][1] <= r) return seg[i][md];
    if(seginf[i][1] >= l and seginf[i][0] <= r){
        if(md == 0) return min(getSeg(l , r , i << 1 , md) , getSeg(l , r , (i << 1) | 1 , md));
        return max(getSeg(l , r , i << 1 , md) , getSeg(l , r , (i << 1) | 1 , md));
    }
    if(md == 0) return n;
    return -1;
}
int bsmx(int l , int r){
    int i = l , j = r;
    l--;
    while(r - l - 1 > 1){
        int c = (r + l + 1) >> 1;
        if(getSeg(i , c , 1 , 1) >= j) r = c;
        else l = c - 1;
    }
    if(r - l - 1 == 1 and getSeg(i , r - 1 , 1 , 1) >= j) return r - 1;
    return r;
}
int bsmn(int l , int r){
    int i = l , j = r;
    r++;
    while(r - l - 1 > 1){
        int c = (r + l + 1) >> 1;
        if(getSeg(c , j , 1 , 0) <= i) l = c - 1;
        else r = c;
    }
    if(r - l - 1 == 1 and getSeg(l + 1 , j , 1 , 0) <= i) return l + 1;
    return l;
}
void f(){
    buildSeg();
    for(int i = 0 ; i < n ; i++){
        if(in[i][0] != -1){
            in[i][0] = bsmx(in[i][0] , i);
        }
        if(in[i][1] != n){
            in[i][1] = bsmn(i , in[i][1]);
        }
    }
    buildSeg();
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    in[0][0] = -1 , in[n - 1][1] = n;
    for(int i = 1 ; i < n ; i++){
        int d;
        cin >> d;
        in[i - 1][1] = d - 1 , in[i][0] = d - 1;
    }
    for(int i = 0 ; i < n ; i++){
        int b;
        cin >> b;
        for(int j = 0 ; j < b ; j++){
            int d;
            cin >> d;
            inxs[d - 1].pb(i);
        }
    }
    init() , f();
    cin >> q;
    for(int i = 0 ; i < q ; i++){
        int v , u;
        cin >> v >> u;
        v-- , u--;
        if(v < u){
            int d = getSeg(v + 1 , u , 1 , 0);
            if(d >= v) cout << "YES\n";
            else cout << "NO\n";
        }else{
            int d = getSeg(u , v - 1 , 1 , 1);
            if(d <= v) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

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