제출 #133056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
133056		rajarshi_basu	Long Mansion (JOI17_long_mansion)	C++14	5 / 100	3069 ms	28072 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];
int n;
int getMaxRightNeeded(int l,int r){
	int mx = 0;
	FORE(i,l,r)mx = max(mx,rightNeeded[i]);
	return mx;
}
int getMinLeftNeeded(int l,int r){
	int mn = n;
	FORE(i,l,r)mn = min(mn,leftNeeded[i]);
	return mn;
}
 
#define endl '\n'
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   
    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]];
    }
    
    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 getMaxRightNeeded(leftNeeded[ed],x-1)> ed)){
        			b = 0;
        			break;
        		}
        	}	
        }else if(x > y){
        	for(int ed = x-1;ed >= y;ed--){
        		if(rightNeeded[ed] == n or (rightNeeded[ed] > x and getMinLeftNeeded(x,rightNeeded[ed]-1) <= ed)){
        			//cout << rightNeeded[ed] << endl;
        			//cout << leftNeeded[rightNeeded[ed]-1] << endl;
        			//cout << ed << endl;
        			b = 0;
        			break;
        		}
        	}
        }
        

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

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