Submission #431556

#	Time	Username	Problem	Language	Result	Execution time	Memory
431556		lyc	Long Mansion (JOI17_long_mansion)	C++14	10 / 100	3064 ms	92012 KiB

long_mansion

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<ll,ll> pll;

const int mxN = 5e5+5;

int N, C[mxN], Q;
set<int> keys[mxN], kright[mxN], k3[mxN];
int goleft[mxN], goright[mxN];

void mergeto(set<int>& a, set<int>& b) {
    if (SZ(a) > SZ(b)) swap(a,b);
    for (auto& x : a) b.insert(x);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    FOR(i,1,N-1){
        cin >> C[i];
    }
    C[0] = C[N] = 1e9+5; // impossible
    FOR(i,1,N){
        int B; cin >> B;
        FOR(j,1,B){
            int A; cin >> A;
            keys[i].insert(A);
        }
    }

    FOR(i,1,N){
        set<int> k;
        for (auto& x : keys[i]) k.insert(x);
        goleft[i] = goright[i] = i;
        while (true) {
            if (k.count(C[goleft[i]-1])) {
                --goleft[i];
                for (auto& x : keys[goleft[i]]) k.insert(x);
            } else if (k.count(C[goright[i]])) {
                ++goright[i];
                for (auto& x : keys[goright[i]]) k.insert(x);
            } else break;
        }
    }

    cin >> Q;
    FOR(i,1,Q){
        int X, Y; cin >> X >> Y;
        cout << (goleft[X] <= Y && Y <= goright[X] ? "YES" : "NO") << '\n';
    }
}

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