Submission #1065923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065923		Unforgettablepl	Long Mansion (JOI17_long_mansion)	C++17	15 / 100	284 ms	71476 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;
        vector<tuple<int,int,int>> left_points;
        vector<tuple<int,int,int>> right_points;
        int cnt = 0;
        for(auto[type,l,r]:limitations[i]) {
            if(type==-1) {
                left_points.emplace_back(l, 1, ++cnt);
                right_points.emplace_back(r, 2, cnt);
            } else if(type==1) {
                left_points.emplace_back(l, 2, ++cnt);
                right_points.emplace_back(r, 2, cnt);
            } else if(type==2) {
                left_points.emplace_back(l, 1, ++cnt);
                right_points.emplace_back(r, 1, cnt);
            }
        }
        sort(left_points.rbegin(),left_points.rend());
        for(auto&[a,b,c]:left_points)if(b==1)b=2;
        else b=1;
        sort(right_points.begin(),right_points.end());
        vector<bool> recieved(21);
        auto iter_l = left_points.begin();
        auto iter_r = right_points.begin();
        while(true) {
            if(iter_l!=left_points.end() and (get<1>(*iter_l)==1 or recieved[get<2>(*iter_l)] )) {
                recieved[get<2>(*iter_l)]=true;
                iter_l++;
            } else if(iter_r!=right_points.end() and (get<1>(*iter_r)==1 or recieved[get<2>(*iter_r)] )) {
                recieved[get<2>(*iter_r)]=true;
                iter_r++;
            } else break;
        }
        if(iter_l==left_points.end())Lbound[i]=1;
        else Lbound[i]=get<0>(*iter_l);
        if(iter_r==right_points.end())Rbound[i]=N;
        else Rbound[i]=get<0>(*iter_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++) {
      |                     ~^~~~~~~~~~~~~~~~
long_mansion.cpp:56:13: warning: unused variable 'L' [-Wunused-variable]
   56 |         int L = 1;
      |             ^
long_mansion.cpp:57:13: warning: unused variable 'R' [-Wunused-variable]
   57 |         int R = N;
      |             ^

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