oj.uz

Submission #889276

# Submission time Handle Problem Language Result Execution time Memory
889276 2023-12-19T09:34:03 Z dimashhh Long Mansion (JOI17_long_mansion) C++17
0 / 100
 182 ms 52576 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;
        }
    }
    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 << (y >= resl[x] && y <= resr[x] ? "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:105:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  105 | main()
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 43868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 43868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 182 ms 52576 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 43868 KB Output isn't correct
2 Halted 0 ms 0 KB -