oj.uz

Submission #917980

# Submission time Handle Problem Language Result Execution time Memory
917980 2024-01-29T09:02:45 Z andrey27_sm Long Mansion (JOI17_long_mansion) C++17
100 / 100
 2494 ms 78456 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 = 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19032 KB Output is correct
2 Correct 15 ms 18880 KB Output is correct
3 Correct 15 ms 19036 KB Output is correct
4 Correct 15 ms 19036 KB Output is correct
5 Correct 14 ms 18872 KB Output is correct
6 Correct 15 ms 18876 KB Output is correct
7 Correct 14 ms 19036 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19032 KB Output is correct
2 Correct 15 ms 18880 KB Output is correct
3 Correct 15 ms 19036 KB Output is correct
4 Correct 15 ms 19036 KB Output is correct
5 Correct 14 ms 18872 KB Output is correct
6 Correct 15 ms 18876 KB Output is correct
7 Correct 14 ms 19036 KB Output is correct
8 Correct 728 ms 20780 KB Output is correct
9 Correct 723 ms 20536 KB Output is correct
10 Correct 752 ms 20960 KB Output is correct
11 Correct 738 ms 21012 KB Output is correct
12 Correct 705 ms 20560 KB Output is correct
13 Correct 731 ms 20836 KB Output is correct
14 Correct 721 ms 20820 KB Output is correct
15 Correct 741 ms 20940 KB Output is correct
16 Correct 717 ms 21020 KB Output is correct
17 Correct 739 ms 25176 KB Output is correct
18 Correct 736 ms 25172 KB Output is correct
19 Correct 737 ms 25152 KB Output is correct
20 Correct 730 ms 25300 KB Output is correct
21 Correct 736 ms 24708 KB Output is correct
22 Correct 732 ms 25324 KB Output is correct
23 Correct 749 ms 25100 KB Output is correct
24 Correct 720 ms 24912 KB Output is correct
25 Correct 728 ms 24976 KB Output is correct
26 Correct 727 ms 24756 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 943 ms 29780 KB Output is correct
2 Correct 896 ms 29580 KB Output is correct
3 Correct 908 ms 29716 KB Output is correct
4 Correct 960 ms 29488 KB Output is correct
5 Correct 923 ms 29512 KB Output is correct
6 Correct 865 ms 29136 KB Output is correct
7 Correct 884 ms 29252 KB Output is correct
8 Correct 854 ms 35408 KB Output is correct
9 Correct 856 ms 35696 KB Output is correct
10 Correct 844 ms 35696 KB Output is correct
11 Correct 853 ms 35668 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 19032 KB Output is correct
2 Correct 15 ms 18880 KB Output is correct
3 Correct 15 ms 19036 KB Output is correct
4 Correct 15 ms 19036 KB Output is correct
5 Correct 14 ms 18872 KB Output is correct
6 Correct 15 ms 18876 KB Output is correct
7 Correct 14 ms 19036 KB Output is correct
8 Correct 728 ms 20780 KB Output is correct
9 Correct 723 ms 20536 KB Output is correct
10 Correct 752 ms 20960 KB Output is correct
11 Correct 738 ms 21012 KB Output is correct
12 Correct 705 ms 20560 KB Output is correct
13 Correct 731 ms 20836 KB Output is correct
14 Correct 721 ms 20820 KB Output is correct
15 Correct 741 ms 20940 KB Output is correct
16 Correct 717 ms 21020 KB Output is correct
17 Correct 739 ms 25176 KB Output is correct
18 Correct 736 ms 25172 KB Output is correct
19 Correct 737 ms 25152 KB Output is correct
20 Correct 730 ms 25300 KB Output is correct
21 Correct 736 ms 24708 KB Output is correct
22 Correct 732 ms 25324 KB Output is correct
23 Correct 749 ms 25100 KB Output is correct
24 Correct 720 ms 24912 KB Output is correct
25 Correct 728 ms 24976 KB Output is correct
26 Correct 727 ms 24756 KB Output is correct
27 Correct 943 ms 29780 KB Output is correct
28 Correct 896 ms 29580 KB Output is correct
29 Correct 908 ms 29716 KB Output is correct
30 Correct 960 ms 29488 KB Output is correct
31 Correct 923 ms 29512 KB Output is correct
32 Correct 865 ms 29136 KB Output is correct
33 Correct 884 ms 29252 KB Output is correct
34 Correct 854 ms 35408 KB Output is correct
35 Correct 856 ms 35696 KB Output is correct
36 Correct 844 ms 35696 KB Output is correct
37 Correct 853 ms 35668 KB Output is correct
38 Correct 1408 ms 60252 KB Output is correct
39 Correct 1385 ms 66464 KB Output is correct
40 Correct 1256 ms 52232 KB Output is correct
41 Correct 1156 ms 64616 KB Output is correct
42 Correct 968 ms 38504 KB Output is correct
43 Correct 997 ms 38012 KB Output is correct
44 Correct 1245 ms 49360 KB Output is correct
45 Correct 1250 ms 50428 KB Output is correct
46 Correct 1264 ms 50772 KB Output is correct
47 Correct 972 ms 38764 KB Output is correct
48 Correct 942 ms 36856 KB Output is correct
49 Correct 1203 ms 47612 KB Output is correct
50 Correct 1260 ms 49256 KB Output is correct
51 Correct 1285 ms 51632 KB Output is correct
52 Correct 1130 ms 53096 KB Output is correct
53 Correct 1318 ms 64544 KB Output is correct
54 Correct 2494 ms 78456 KB Output is correct
55 Correct 1254 ms 65880 KB Output is correct