oj.uz

Submission #889278

# Submission time Handle Problem Language Result Execution time Memory
889278 2023-12-19T09:37:54 Z dimashhh Long Mansion (JOI17_long_mansion) C++17
100 / 100
 1837 ms 177892 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1, MOD = 998244353;
typedef long long ll;

int n,q,c[N],b[N],resl[N],resr[N];
vector<int> a[N];
int used[N],timer = 0;
multiset<pair<int,pair<int,int>>> cur;
vector<int> L[N],R[N];
void go(int l,int r){
    if(l >= r) return;
    int mid = (l + r) >> 1;
    go(l,mid);
    go(mid + 1,r);
    timer++;
    int it = mid;
    for(int j:a[it]){
        used[j] = timer;
    }
    for(int i = mid + 1;i <= r;i++){
        for(int j:a[i]){
            used[j] = timer;
        }
        while(it >= l && used[c[it - 1]] == timer){
            it--;
            for(int j:a[it]){
                used[j] = timer;
            }
        }
        if(used[c[i]] == timer) continue;
        if(it >= l){
            L[it].push_back(i);
            R[i].push_back(it);
        }
    }
    timer++;
    it = mid + 1;
    for(int j:a[it]){
        used[j] = timer;
    }
    for(int i = mid;i >= l;i--){
        for(int j:a[i]){
            used[j] = timer;
        }
        while(it <= r && used[c[it]] == timer){
            it++;
            for(int j:a[it]){
                used[j] = timer;
            }
        }
        if(used[c[i - 1]] == timer) continue;
        if(it <= r){
            R[it].push_back(i);
            L[i].push_back(it);
        }
    }
}

void test(){
    cin >> n;
    for(int i = 1;i <= n - 1;i++){
        cin >> c[i];
    }
    for(int i = 1;i <= n;i++){
        cin >> b[i];
        for(int j = 1;j <=b[i];j++){
            int x;
            cin >> x;
            used[x] = i;
            a[i].push_back(x);
        }
        if(used[c[i]] != i && used[c[i - 1]] != i){
            resl[i] = i;
            resr[i] = i;
            L[i].push_back(i);
            R[i].push_back(i);
        }
    }
    for(int i = 1;i <= n;i++){
        used[i] = 0;
    }
    L[1].push_back(n);
    R[n].push_back(1);
    go(1,n);
    for(int i = 1;i <=n;i++){
        for(int j:L[i]){
            cur.insert({j - i + 1,{i,j}});
        }
        if(!cur.empty()){
            resl[i] = (*cur.begin()).second.first;
            resr[i] = (*cur.begin()).second.second;
        }
        for(int j:R[i]){
            cur.erase(cur.find({i - j + 1,{j,i}}));
        }
    }
    int q;
    cin >> q;
    while(q--){
        int x,y;
        cin >> x >> y;
        // cout << resl[x] << ' ' << resr[x] << '\n';
        cout << (y >= resl[x] && y <= resr[x] ? "YES\n":"NO\n");
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1; // cin >> T;
    while (T--)
        test();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 43864 KB Output is correct
2 Correct 11 ms 43868 KB Output is correct
3 Correct 11 ms 43976 KB Output is correct
4 Correct 10 ms 43608 KB Output is correct
5 Correct 10 ms 43612 KB Output is correct
6 Correct 10 ms 43740 KB Output is correct
7 Correct 12 ms 43960 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 43864 KB Output is correct
2 Correct 11 ms 43868 KB Output is correct
3 Correct 11 ms 43976 KB Output is correct
4 Correct 10 ms 43608 KB Output is correct
5 Correct 10 ms 43612 KB Output is correct
6 Correct 10 ms 43740 KB Output is correct
7 Correct 12 ms 43960 KB Output is correct
8 Correct 82 ms 45212 KB Output is correct
9 Correct 80 ms 45648 KB Output is correct
10 Correct 74 ms 45388 KB Output is correct
11 Correct 79 ms 45660 KB Output is correct
12 Correct 68 ms 45648 KB Output is correct
13 Correct 74 ms 45392 KB Output is correct
14 Correct 71 ms 45416 KB Output is correct
15 Correct 78 ms 45392 KB Output is correct
16 Correct 71 ms 45712 KB Output is correct
17 Correct 76 ms 45356 KB Output is correct
18 Correct 72 ms 45444 KB Output is correct
19 Correct 80 ms 45460 KB Output is correct
20 Correct 72 ms 45652 KB Output is correct
21 Correct 83 ms 45648 KB Output is correct
22 Correct 76 ms 45396 KB Output is correct
23 Correct 76 ms 45480 KB Output is correct
24 Correct 75 ms 45436 KB Output is correct
25 Correct 77 ms 45452 KB Output is correct
26 Correct 74 ms 45536 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 54264 KB Output is correct
2 Correct 183 ms 53232 KB Output is correct
3 Correct 168 ms 52308 KB Output is correct
4 Correct 187 ms 53852 KB Output is correct
5 Correct 185 ms 53608 KB Output is correct
6 Correct 131 ms 49512 KB Output is correct
7 Correct 116 ms 48984 KB Output is correct
8 Correct 119 ms 48868 KB Output is correct
9 Correct 114 ms 48940 KB Output is correct
10 Correct 110 ms 48900 KB Output is correct
11 Correct 108 ms 48872 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 43864 KB Output is correct
2 Correct 11 ms 43868 KB Output is correct
3 Correct 11 ms 43976 KB Output is correct
4 Correct 10 ms 43608 KB Output is correct
5 Correct 10 ms 43612 KB Output is correct
6 Correct 10 ms 43740 KB Output is correct
7 Correct 12 ms 43960 KB Output is correct
8 Correct 82 ms 45212 KB Output is correct
9 Correct 80 ms 45648 KB Output is correct
10 Correct 74 ms 45388 KB Output is correct
11 Correct 79 ms 45660 KB Output is correct
12 Correct 68 ms 45648 KB Output is correct
13 Correct 74 ms 45392 KB Output is correct
14 Correct 71 ms 45416 KB Output is correct
15 Correct 78 ms 45392 KB Output is correct
16 Correct 71 ms 45712 KB Output is correct
17 Correct 76 ms 45356 KB Output is correct
18 Correct 72 ms 45444 KB Output is correct
19 Correct 80 ms 45460 KB Output is correct
20 Correct 72 ms 45652 KB Output is correct
21 Correct 83 ms 45648 KB Output is correct
22 Correct 76 ms 45396 KB Output is correct
23 Correct 76 ms 45480 KB Output is correct
24 Correct 75 ms 45436 KB Output is correct
25 Correct 77 ms 45452 KB Output is correct
26 Correct 74 ms 45536 KB Output is correct
27 Correct 195 ms 54264 KB Output is correct
28 Correct 183 ms 53232 KB Output is correct
29 Correct 168 ms 52308 KB Output is correct
30 Correct 187 ms 53852 KB Output is correct
31 Correct 185 ms 53608 KB Output is correct
32 Correct 131 ms 49512 KB Output is correct
33 Correct 116 ms 48984 KB Output is correct
34 Correct 119 ms 48868 KB Output is correct
35 Correct 114 ms 48940 KB Output is correct
36 Correct 110 ms 48900 KB Output is correct
37 Correct 108 ms 48872 KB Output is correct
38 Correct 1400 ms 161680 KB Output is correct
39 Correct 1197 ms 166056 KB Output is correct
40 Correct 927 ms 123060 KB Output is correct
41 Correct 271 ms 83028 KB Output is correct
42 Correct 179 ms 60624 KB Output is correct
43 Correct 132 ms 57752 KB Output is correct
44 Correct 181 ms 63884 KB Output is correct
45 Correct 177 ms 63556 KB Output is correct
46 Correct 164 ms 62996 KB Output is correct
47 Correct 117 ms 56404 KB Output is correct
48 Correct 116 ms 56140 KB Output is correct
49 Correct 184 ms 62292 KB Output is correct
50 Correct 158 ms 62544 KB Output is correct
51 Correct 166 ms 62704 KB Output is correct
52 Correct 759 ms 109756 KB Output is correct
53 Correct 1134 ms 140664 KB Output is correct
54 Correct 1837 ms 177892 KB Output is correct
55 Correct 1192 ms 146732 KB Output is correct