Submission #1236225

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236225		MarwenElarbi	Long Mansion (JOI17_long_mansion)	C++20	25 / 100	566 ms	52324 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int nax=5e5+5;
int lst[nax];
int main() {
    int n;
    cin>>n;
    vector<int> tab[2*n];
    for (int i = 0; i < n-1; ++i)
    {
        int x;
        cin>>x;
        tab[i*2+1].push_back(x);
    }    
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin>>x;
        for (int j = 0; j < x; ++j)
        {
            int y;
            cin>>y;
            tab[i*2].push_back(y);
        }
    }
    for (int i = 0; i < nax; ++i) lst[i]=-1;
    vector <pair<pair<int,int>,int>> cnt;
    for (int i = 0; i < 2*n-1; ++i)
    {
        if(i%2){
            cnt.push_back({{i,0},lst[tab[i][0]]}); 
        }else{
            for(auto u:tab[i]) {
                lst[u]=i;
            }
        }
    }
    for (int i = 0; i < 2*n-1; ++i) lst[i]=2*n-1;
    for (int i = 2*n-2; i >= 0; --i)
    {
        if(i%2){
            cnt.push_back({{lst[tab[i][0]],2},i});
            cnt.push_back({{i,1},lst[tab[i][0]]}); 
        }else{
            for(auto u:tab[i]) lst[u]=i;
        }
    }
    cnt.push_back({{-1,1},2*n-1});
    cnt.push_back({{2*n-1,0},-1});
    sort(cnt.begin(),cnt.end());
    stack<int> cur;
    set<pair<int,int>> st;
    vector<pair<int,int>> ans(n*2);
    int j=-1;
    for (int i = 0; i < cnt.size(); ++i)
    {
        while(j<=cnt[i].fi.fi){
            if(j%2==0) cur.push(j);
            j++;
        }
        if(cnt[i].fi.se==2){
            st.erase({cnt[i].se,cnt[i].fi.fi});
        }else if(cnt[i].fi.se==1) {
            st.insert({cnt[i].fi.fi,cnt[i].se});
        }else{
            while(!cur.empty()){
                pair<int,int> x= *--st.lower_bound(make_pair(cur.top(),0));
                if(x.fi<cnt[i].se) break;
                ans[cur.top()]={x.fi,cnt[i].fi.fi};
                cur.pop();
            }
        }
    }
    int q;
    cin>>q;
    for (int i = 0; i < q; ++i)
    {
        int l,r;
        cin>>l>>r;
        l--;r--;l*=2;r*=2;
        if(ans[l].fi<=r&&r<=ans[l].se) cout <<"YES"<<endl;
        else cout <<"NO"<<endl;
    }
}

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