Submission #1065894

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065894		Unforgettablepl	Long Mansion (JOI17_long_mansion)	C++17	0 / 100	215 ms	55576 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e18;


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> C(N+1);
    vector<vector<int>> keys(N+1);
    vector<vector<pair<int,int>>> items(21);
    for(int i=1;i<N;i++) {
        cin>>C[i];
        items[C[i]].emplace_back(i,2);
    }
    for(int i=1;i<=N;i++) {
        int b;cin>>b;
        keys[i].resize(b);
        for(int&j:keys[i]) {
            cin>>j;
            items[j].emplace_back(i,1);
        }
    }
    vector<vector<tuple<int,int,int>>> limitations(N+1);
    for(int i=1;i<=20;i++) {
        items[i].emplace_back(0,2);
        items[i].emplace_back(N,2);
        sort(items[i].begin(),items[i].end());
        for(int j=1;j<items[i].size();j++) {
            if(items[i][j].second==items[i][j-1].second) {
                if(items[i][j].second==1)continue;
                for(int x=items[i][j-1].first+1;x<=items[i][j].first;x++) {
                    limitations[x].emplace_back(-1,items[i][j-1].first+1,items[i][j].first);
                }
            } else {
                if(items[i][j-1].second==1) {
                    for(int x=items[i][j-1].first;x<=items[i][j].first;x++) {
                        limitations[x].emplace_back(1,items[i][j-1].first,items[i][j].first);
                    }
                } else {
                    for(int x=items[i][j-1].first+1;x<=items[i][j].first;x++) {
                        limitations[x].emplace_back(2,items[i][j-1].first+1,items[i][j].first);
                    }
                }
            }
        }
    }
    vector<int> Lbound(N+1);
    vector<int> Rbound(N+1);
    for(int i=1;i<=N;i++) {
        int L = 1;
        int R = N;
        for(int iterations=1;iterations<=20;iterations++) {
            for(auto[type,l,r]:limitations[i]) {
                if(type==-1) {
                    L=max(L,l);
                    R=min(R,r);
                } else if(type==1) {
                    if(l<L)R=min(R,r);
                } else if(type==2) {
                    if(R<r)L=max(L,l);
                }
            }
        }
        Lbound[i]=L;
        Rbound[i]=R;
    }
    int Q;
    cin >> Q;
    for(int i=1;i<=Q;i++) {
        int X,Y;cin>>X>>Y;
        if(Lbound[X]<=Y and Y<=Rbound[X])cout<<"YES\n";
        else cout << "NO\n";
    }
}

Compilation message (stderr)

long_mansion.cpp: In function 'int32_t main()':
long_mansion.cpp:34:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int j=1;j<items[i].size();j++) {
      |                     ~^~~~~~~~~~~~~~~~

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