Submission #889265

#	Time	Username	Problem	Language	Result	Execution time	Memory
889265		dimashhh	Long Mansion (JOI17_long_mansion)	C++17	25 / 100	527 ms	262144 KiB

long_mansion

#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);
    R[n].push_back(1);
    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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 0 / 75