Submission #133044

#	Time	Username	Problem	Language	Result	Execution time	Memory
133044		rajarshi_basu	Long Mansion (JOI17_long_mansion)	C++14	0 / 100	3015 ms	20460 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--;
        bool b = 1;
        if(x < y){
        	FORE(ed,x,y-1){
        		if(leftNeeded[ed] == -1 or (leftNeeded[ed] < x and rightNeeded[leftNeeded[ed]] > ed)){
        			b = 0;
        			break;
        		}
        	}	
        }else if(x > y){
        	for(int ed = x-1;ed >= y;ed--){
        		if(rightNeeded[x] == n or (rightNeeded[ed] > x and leftNeeded[rightNeeded[ed]-1] <= ed)){
        			b = 0;
        			break;
        		}
        	}
        }
        

        if(b){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
    return 0;
}

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