oj.uz

Submission #889264

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

int n,q,c[N],b[N];
vector<array<int,3>> res(N);
vector<int> a[N];
int used[N],timer = 0;
unordered_map<int,int> is[N];
vector<pair<int,int>> all;
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){
            all.push_back({it,i});
            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){
            all.push_back({i,it});
            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;
            is[i][x] = 1;
            a[i].push_back(x);
        }
        if(!is[i].count(c[i]) && !is[i].count(c[i - 1])){
            array<int,3> f;
            f = {1,i,i};
            res[i] = f;
            L[i].push_back(i);
            R[i].push_back(i);
            all.push_back({i,i});
        }
    }
    L[1].push_back(n);
    all.push_back({1,n});
    go(1,n);
    for(int i = 1;i <=n;i++){
        for(int j:L[i]){
            cur.insert({j - i + 1,{i,j}});
        }
        res[i][1] = (*cur.begin()).second.first;
        res[i][2] = (*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 << (y >= res[x][1] && y <= res[x][2] ? "YES\n":"NO\n");
    }
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1; // cin >> T;
    while (T--)
        test();
}

Compilation message

long_mansion.cpp:108:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  108 | main()
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 74844 KB Output is correct
2 Correct 20 ms 74844 KB Output is correct
3 Correct 20 ms 75100 KB Output is correct
4 Correct 18 ms 74588 KB Output is correct
5 Correct 18 ms 74840 KB Output is correct
6 Correct 18 ms 74588 KB Output is correct
7 Correct 22 ms 75040 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 74844 KB Output is correct
2 Correct 20 ms 74844 KB Output is correct
3 Correct 20 ms 75100 KB Output is correct
4 Correct 18 ms 74588 KB Output is correct
5 Correct 18 ms 74840 KB Output is correct
6 Correct 18 ms 74588 KB Output is correct
7 Correct 22 ms 75040 KB Output is correct
8 Correct 85 ms 76252 KB Output is correct
9 Correct 84 ms 76224 KB Output is correct
10 Correct 82 ms 78932 KB Output is correct
11 Correct 83 ms 79416 KB Output is correct
12 Correct 81 ms 78160 KB Output is correct
13 Correct 79 ms 78888 KB Output is correct
14 Correct 79 ms 78932 KB Output is correct
15 Correct 82 ms 78572 KB Output is correct
16 Correct 98 ms 78860 KB Output is correct
17 Correct 79 ms 78708 KB Output is correct
18 Correct 80 ms 78888 KB Output is correct
19 Correct 91 ms 78796 KB Output is correct
20 Correct 79 ms 78776 KB Output is correct
21 Correct 78 ms 78868 KB Output is correct
22 Correct 82 ms 78572 KB Output is correct
23 Correct 83 ms 78796 KB Output is correct
24 Correct 84 ms 78796 KB Output is correct
25 Correct 83 ms 78796 KB Output is correct
26 Correct 90 ms 78720 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 114176 KB Output is correct
2 Correct 267 ms 112836 KB Output is correct
3 Correct 254 ms 110256 KB Output is correct
4 Correct 269 ms 114172 KB Output is correct
5 Correct 253 ms 113740 KB Output is correct
6 Correct 167 ms 100556 KB Output is correct
7 Correct 185 ms 99664 KB Output is correct
8 Correct 148 ms 99664 KB Output is correct
9 Correct 149 ms 99560 KB Output is correct
10 Correct 156 ms 99652 KB Output is correct
11 Correct 147 ms 99612 KB Output is correct

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 74844 KB Output is correct
2 Correct 20 ms 74844 KB Output is correct
3 Correct 20 ms 75100 KB Output is correct
4 Correct 18 ms 74588 KB Output is correct
5 Correct 18 ms 74840 KB Output is correct
6 Correct 18 ms 74588 KB Output is correct
7 Correct 22 ms 75040 KB Output is correct
8 Correct 85 ms 76252 KB Output is correct
9 Correct 84 ms 76224 KB Output is correct
10 Correct 82 ms 78932 KB Output is correct
11 Correct 83 ms 79416 KB Output is correct
12 Correct 81 ms 78160 KB Output is correct
13 Correct 79 ms 78888 KB Output is correct
14 Correct 79 ms 78932 KB Output is correct
15 Correct 82 ms 78572 KB Output is correct
16 Correct 98 ms 78860 KB Output is correct
17 Correct 79 ms 78708 KB Output is correct
18 Correct 80 ms 78888 KB Output is correct
19 Correct 91 ms 78796 KB Output is correct
20 Correct 79 ms 78776 KB Output is correct
21 Correct 78 ms 78868 KB Output is correct
22 Correct 82 ms 78572 KB Output is correct
23 Correct 83 ms 78796 KB Output is correct
24 Correct 84 ms 78796 KB Output is correct
25 Correct 83 ms 78796 KB Output is correct
26 Correct 90 ms 78720 KB Output is correct
27 Correct 261 ms 114176 KB Output is correct
28 Correct 267 ms 112836 KB Output is correct
29 Correct 254 ms 110256 KB Output is correct
30 Correct 269 ms 114172 KB Output is correct
31 Correct 253 ms 113740 KB Output is correct
32 Correct 167 ms 100556 KB Output is correct
33 Correct 185 ms 99664 KB Output is correct
34 Correct 148 ms 99664 KB Output is correct
35 Correct 149 ms 99560 KB Output is correct
36 Correct 156 ms 99652 KB Output is correct
37 Correct 147 ms 99612 KB Output is correct
38 Runtime error 444 ms 262144 KB Execution killed with signal 9
39 Halted 0 ms 0 KB -