oj.uz

Submission #917974

# Submission time Handle Problem Language Result Execution time Memory
917974 2024-01-29T08:43:41 Z andrey27_sm Long Mansion (JOI17_long_mansion) C++17
5 / 100
 917 ms 37008 KB 
#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 = max(i,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";
    // }
    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19100 KB Output is correct
2 Correct 15 ms 19036 KB Output is correct
3 Correct 20 ms 19548 KB Output is correct
4 Correct 15 ms 19036 KB Output is correct
5 Correct 16 ms 19036 KB Output is correct
6 Correct 16 ms 19172 KB Output is correct
7 Correct 14 ms 19036 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19100 KB Output is correct
2 Correct 15 ms 19036 KB Output is correct
3 Correct 20 ms 19548 KB Output is correct
4 Correct 15 ms 19036 KB Output is correct
5 Correct 16 ms 19036 KB Output is correct
6 Correct 16 ms 19172 KB Output is correct
7 Correct 14 ms 19036 KB Output is correct
8 Correct 728 ms 24740 KB Output is correct
9 Correct 753 ms 24708 KB Output is correct
10 Correct 744 ms 25184 KB Output is correct
11 Correct 738 ms 25684 KB Output is correct
12 Correct 749 ms 24572 KB Output is correct
13 Correct 820 ms 24960 KB Output is correct
14 Correct 753 ms 25428 KB Output is correct
15 Correct 737 ms 25172 KB Output is correct
16 Incorrect 721 ms 24924 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 917 ms 36988 KB Output is correct
2 Correct 902 ms 36648 KB Output is correct
3 Correct 887 ms 36556 KB Output is correct
4 Correct 909 ms 36804 KB Output is correct
5 Correct 904 ms 37008 KB Output is correct
6 Correct 855 ms 35636 KB Output is correct
7 Incorrect 859 ms 35480 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19100 KB Output is correct
2 Correct 15 ms 19036 KB Output is correct
3 Correct 20 ms 19548 KB Output is correct
4 Correct 15 ms 19036 KB Output is correct
5 Correct 16 ms 19036 KB Output is correct
6 Correct 16 ms 19172 KB Output is correct
7 Correct 14 ms 19036 KB Output is correct
8 Correct 728 ms 24740 KB Output is correct
9 Correct 753 ms 24708 KB Output is correct
10 Correct 744 ms 25184 KB Output is correct
11 Correct 738 ms 25684 KB Output is correct
12 Correct 749 ms 24572 KB Output is correct
13 Correct 820 ms 24960 KB Output is correct
14 Correct 753 ms 25428 KB Output is correct
15 Correct 737 ms 25172 KB Output is correct
16 Incorrect 721 ms 24924 KB Output isn't correct
17 Halted 0 ms 0 KB -