Submission #206992

#	Time	Username	Problem	Language	Result	Execution time	Memory
206992		nvmdava	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	3070 ms	16632 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 524288
#define MOD 1000000007
#define INF 0x3f3f3f3f

int c[N];
int n;

vector<int> loc[N];

int le[N], ri[N];

bool query(int l, int r, int c){
    auto it = lower_bound(loc[c].begin(), loc[c].end(), l);
    return it != loc[c].end() && *it <= r;
}

void dnc(int l, int r){
    if(l > r) return;
    int m = (l + r) >> 1;
    int L = m, R = m;
    bool ok;
    do {
        ok = 0;
        while(query(L, R, c[R])){
            ++R;
            ok = 1;
            if(ri[R]){
                L = min(L, le[R]);
                R = max(R, ri[R]);
            }
        }
        while(query(L, R, c[L - 1])){
            --L;
            ok = 1;
            if(le[L]){
                R = max(R, ri[L]);
                L = min(L, le[L]);
            }
        }
    } while (ok == 1);
    le[m] = L;
    ri[m] = R;
    dnc(l, m - 1);
    dnc(m + 1, r);
}

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

    cin>>n;
    for(int i = 1; i < n; ++i){
        cin>>c[i];
    }
    for(int b, k, i = 1; i <= n; ++i){
        cin>>b;
        while(b--){
            cin>>k;
            loc[k].push_back(i);
        }
    }
    dnc(1, n);
    int q;
    cin>>q;
    while(q--){
        int x, y;
        cin>>x>>y;
        if(le[x] <= y && y <= ri[x])
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
}

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