제출 #917980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
917980		andrey27_sm	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	2494 ms	78456 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
int c[500007];
vector<int> keys[500007];
struct sgt_max {
    vector<int> tree;
    int n;
    void init(int n) {
        this->n = n;
        tree.resize(n * 4);
    }
    void update(int v, int l, int r, int pos, int val) {
        if(r < pos || l > pos) return;
        if (l == r) {
            tree[v] = val;
            return;
        }
        int mid = (l + r) / 2;
        update(v * 2, l, mid, pos, val);
        update(v * 2 + 1, mid + 1, r, pos, val);
        tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
    }
    int get(int v, int l, int r, int L, int R) {
        if (r < L || l > R) return 0;
        if (l >= L && r <= R) return tree[v];
        int mid = (l + r) / 2;
        return max(get(v * 2, l, mid, L, R), get(v * 2 + 1, mid + 1, r, L, R));
    }

    int prev_larger(int v,int l,int r,int k,int val) {
        int m = (l + r) / 2;
        if(tree[v] <= val or k < l) return -1;
        if(l == r) {
            if(tree[v] > val) return l;
            return -1;
        }
        if(k <= m) {
            return prev_larger(v * 2, l, m, k, val);
        }
        int right_part = prev_larger(v * 2 + 1, m + 1, r, k, val);
        if(right_part != -1) {
            return right_part;
        }
        return prev_larger(v * 2, l, m, m, val);
    }
};
struct sgt_min {
    vector<int> tree;
    int n{};
    void init(int n) {
        this->n = n;
        tree.resize(n * 4);
    }
    void update(int v, int l, int r, int pos, int val) {
        if(r < pos || l > pos) return;
        if (l == r) {
            tree[v] = val;
            return;
        }
        int mid = (l + r) / 2;
        update(v * 2, l, mid, pos, val);
        update(v * 2 + 1, mid + 1, r, pos, val);
        tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
    }
    int get(int v, int l, int r, int L, int R) {
        if (r < L || l > R) return 1e9;
        if (l >= L && r <= R) return tree[v];
        int mid = (l + r) / 2;
        return min(get(v * 2, l, mid, L, R), get(v * 2 + 1, mid + 1, r, L, R));
    }
    int next_smaller(int v,int l,int r,int k,int val) {
        int m = (l + r) / 2;
        if(tree[v] >= val or r < k) return -1;
        if(l == r) {
            if(tree[v] < val) return l;
            return -1;
        }
        if(k > m) {
            return next_smaller(v * 2 + 1, m + 1, r, k, val);
        }
        int left_part = next_smaller(v * 2, l, m, k, val);
        if(left_part != -1) {
            return left_part;
        }
        return next_smaller(v * 2 + 1, m + 1, r, m+1, val);
    }
};
pair<int,int> reachable[500007];
int next_r[500007];
int prev_r[500007];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n-1;i++) {
        cin >> c[i];
    }
    for(int i = 0;i < n;i++) {
        int k;
        cin >> k;
        for (int j = 0;j < k;j++) {
            int x;
            cin >> x;
            keys[i].push_back(x);
        }
        reachable[i] = {i,i};
    }
    sgt_max sgt_max;
    sgt_max.init(n);
    sgt_min sgt_min;
    sgt_min.init(n);
    map<int,int> mp;
    for(int i = 0;i < n-1;i++) {
        for(auto e:keys[i]) {
            mp[e] = i;
        }
        if(mp.find(c[i]) != mp.end()) {
            sgt_min.update(1,0,n-1,i,mp[c[i]]);
            prev_r[i] = mp[c[i]];
        }
        else {
            sgt_min.update(1,0,n-1,i,-1);
            prev_r[i] = -1;
        }
    }
    mp.clear();
    for(int i = n-2;i >= 0;i--) {
        for(auto e:keys[i+1]) {
            mp[e] = i+1;
        }
        if(mp.find(c[i]) != mp.end()) {
            sgt_max.update(1,0,n-1,i+1,mp[c[i]]);
            next_r[i] = mp[c[i]];
        }
        else {
            sgt_max.update(1,0,n-1,i+1,n);
            next_r[i] = n;
        }
    }
    for(int i = 0;i < n;i++) {
        int R = sgt_min.next_smaller(1,0,n-1,i,reachable[i].second);
        if(R != -1) {
            reachable[i].second = R;
        }
        else {
            reachable[i].second = n-1;
        }
        if(i and next_r[i-1] <= R) {
            int L = reachable[i-1].first;
            R = max(R,reachable[i-1].second);
            int tmpL = L;
            int tmpR = R;
            do {
                L = tmpL;
                R = tmpR;
                tmpL = sgt_max.prev_larger(1,0,n-1,L,R);
                if(tmpL == -1) tmpL = 0;
                tmpR = sgt_min.next_smaller(1,0,n-1,R,tmpL);
                if(tmpR == -1) tmpR = n-1;
            }while (tmpL != L or tmpR != R);
            reachable[i].first = L;
            reachable[i].second = R;
        }
    }
    for(int i = 0;i < n;i++) {
         //cerr << reachable[i].first << " " << reachable[i].second << "\n";
    }
    /*for(int i = 0;i < n;i++) {
        int L = i;
        int R = i;
        int tmpL = L;
        int tmpR = R;
        do{
            L = tmpL;
            R = tmpR;
            tmpL = sgt_max.prev_larger(1,0,n-1,L,R);
            if(tmpL == -1)
                tmpL = 0;
            tmpR = sgt_min.next_smaller(1,0,n-1,R,tmpL);
            if(tmpR == -1)
                tmpR = n-1;
        }while (tmpL != L or tmpR != R);
        reachable[i].first = L;
        reachable[i].second = R;
        cerr << L << " " << R << "\n";
    }*/
    int q;
    cin >> q;
    for(int i = 0;i < q;i++) {
        int l,r;
        cin >> l >> r;
        l--;
        r--;
        if(reachable[l].first <= r and reachable[l].second >= r) {
            cout << "YES\n";
        }
        else {
            cout << "NO\n";
        }
    }
}

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