Submission #1235824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235824		MarwenElarbi	Long Mansion (JOI17_long_mansion)	C++20	0 / 100	1 ms	2368 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() {
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    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({{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());
    //for(auto u:cnt) cout <<u.fi.fi<<" "<<u.se<<" "<<u.fi.se<<endl;
    stack<pair<int,int>> st;
    vector<pair<int,int>> intersection;
    vector<pair<int,int>> ans(2*n);
    for (int i = 0; i < 2*n; ++i) ans[i]={-1,2*n-1};
    int lst = -1;
    for (int i = 0; i < cnt.size(); ++i)
    {
        if(cnt[i].fi.se==1) {
            st.push({cnt[i].fi.fi,cnt[i].se});
        }else{
            while(!st.empty()&&st.top().se<cnt[i].fi.fi){
                st.pop();
            }
            pair<int,int> nab={-1,-1};
            if(!st.empty()) nab=st.top();
            bool test=false;
            int y = cnt[i].fi.fi;
            //cout <<y<<endl;
            while(!st.empty()){
                while(!st.empty()&&st.top().se<cnt[i].fi.fi){
                    st.pop();
                }if(st.empty()) break;
                if(st.top().fi<cnt[i].se){
                    if(!test) nab={-1,-1};
                    break;
                }
                test=true;
                int x = y; 
                while(x > max(st.top().fi,lst) ){
                    if(x%2==0){
                        ans[x]={st.top().fi,cnt[i].fi.fi};
                    } 
                    x--;
                }
                y=x;
                intersection.push_back({st.top().fi,cnt[i].fi.fi});
                st.pop();
            }
            if(nab!=make_pair(-1,-1)){
                st.push(nab);
                lst=cnt[i].fi.fi;
            } 
        }
        
    }
    //for(auto u:intersection) cout << u.fi <<" "<<u.se<<endl;
    sort(intersection.begin(),intersection.end());
    //for(auto u:intersection) cout <<u.fi<<" "<<u.se<<endl;
    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;
        /*int cur=lower_bound(intersection.begin(),intersection.end(),make_pair(l,0))-intersection.begin();
        cur--;
        cur=lower_bound(intersection.begin(),intersection.end(),make_pair(intersection[cur].fi,l))-intersection.begin();
        cout<< cur<<" "<<intersection[cur].fi<<" "<<intersection[cur].se<<endl;
        if(intersection[cur].fi<=r&&r<=intersection[cur].se) cout <<"YES"<<endl;
        else cout << "NO" <<endl;*/
    }
}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:9:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |         freopen("input.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen("output.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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