Submission #122142

#	Time	Username	Problem	Language	Result	Execution time	Memory
122142		rajarshi_basu	Long Mansion (JOI17_long_mansion)	C++14	25 / 100	3035 ms	52348 KiB

long_mansion

#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <random>
#include <stack>
#include <chrono>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>
#define vv vector

using namespace std;

const int MAXN = 5e5+10;
int C[MAXN];
int leftNeeded[MAXN];
int rightNeeded[MAXN];
vi keys[MAXN];
int L[MAXN];
int R[MAXN];
int last[MAXN];

#define endl '\n'
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    FOR(i,n-1)cin >> C[i];
    FOR(i,n){
        int x;cin >> x;
        FOR(j,x){
            int y;cin >> y;
            keys[i].pb(y);
        }
    }

    // input taking is done, now find left and right needed values for each edge.
    FOR(i,MAXN)last[i] = -1;
    FOR(i,n-1){
        for(auto e : keys[i]){
            last[e] = i;
        }
        leftNeeded[i] = last[C[i]];
    }
    FOR(i,MAXN)last[i] = n;
    for(int i = n-1;i>0;i--){
        for(auto e : keys[i])last[e] = i;
        rightNeeded[i-1] = last[C[i-1]];
    }
    FOR(i,n-1){
      //  cout << leftNeeded[i] << " " << rightNeeded[i] << endl;
    }
    //cout << endl;
    // we have found out the left and right needed. now we need to compute all the ranges.
    FOR(i,n){
        int rightl = (i == 0)?-1:R[i-1];
        if(rightl >= i){
            // we know that we cannot escape from this box anyway. 
            // now try to go left once.
            int minR = rightNeeded[i-1];
            int ind = -1;
            FORE(edge,i,min(rightl-1,minR-1)){
                if(leftNeeded[edge] < i){
                    ind = edge;
                    break;
                }
            }
            if(minR > rightl and ind == -1)ind = rightl;
            if(ind == -1){
                L[i] = L[i-1];
                R[i] = R[i-1];

            }else{
                L[i] = i;
                R[i] = ind;
            }
        }else{
            // try increasing right ptr one by one. and for each such move, increase left pointer as much as possible.
            int lptr = i;
            int rptr = i;
            while(rptr < n){
                while(lptr > 0 and rightNeeded[lptr-1] <= rptr)lptr--;
                if(leftNeeded[rptr] < lptr)break;
                rptr++;
            }
            L[i] = lptr;
            R[i] = rptr;
        }
      //  cout << L[i] << " " << R[i] << endl;
    }
   
    int q;
    cin >> q;
    //cout << q << endl;
    FOR(i,q){
        int x,y;
        cin >> x >> y;
        x--;y--;
        if(L[x] <= y and y <= R[x]){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
    return 0;
}

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