답안 #917980

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
917980	2024-01-29T09:02:45 Z	andrey27_sm	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	2494 ms	78456 KB

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.0 / 5.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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