Submission #206990

#	Time	Username	Problem	Language	Result	Execution time	Memory
206990		nvmdava	Long Mansion (JOI17_long_mansion)	C++17	10 / 100	3048 ms	38032 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> key[1048576];

void build(int id, int l, int r){
    if(l == r){
        sort(key[id].begin(), key[id].end());
        key[id].resize(unique(key[id].begin(), key[id].end()) - key[id].begin());
        return;
    }
    int id1 = id << 1, id2 = id << 1 | 1, i1 = 0, i2 = 0, m = (l + r) >> 1;
    build(id1, l, m);
    build(id2, m + 1, r);
    int sz1 = key[id1].size(), sz2 = key[id2].size();
    while(i1 != sz1 && i2 != sz2){
        if(key[id1][i1] == key[id2][i2]){
            key[id].push_back(key[id1][i1++]);
            ++i2;
        } else if(key[id1][i1] < key[id2][i2]){
            key[id].push_back(key[id1][i1++]);
        } else {
            key[id].push_back(key[id2][i2++]);
        }
    }
    while(i1 != sz1)
        key[id].push_back(key[id1][i1++]);
    while(i2 != sz2)
        key[id].push_back(key[id2][i2++]);
}

bool query(int id, int l, int r, int L, int R, int c){
    if(l > R || r < L) return 0;
    if(L <= l && r <= R){
        auto it = lower_bound(key[id].begin(), key[id].end(), c);
        return it != key[id].end() && *it == c;
    }
    int m = (l + r) >> 1;
    return query(id << 1, l, m, L, R, c) || query(id << 1 | 1, m + 1, r, L, R, c);
}

int le[N], ri[N];

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(1, 1, N, L, R, c[R])){
            ++R;
            ok = 1;
            if(ri[R]){
                L = min(L, le[R]);
                R = max(R, ri[R]);
            }
        }
        while(query(1, 1, N, 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;
            key[i + N - 1].push_back(k);
        }
    }
    build(1, 1, N);
    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