제출 #889276

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
889276		dimashhh	Long Mansion (JOI17_long_mansion)	C++17	0 / 100	182 ms	52576 KiB

long_mansion

#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();
}

컴파일 시 표준 에러 (stderr) 메시지

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

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