Submission #370626

#	Time	Username	Problem	Language	Result	Execution time	Memory
370626		balbit	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	1407 ms	130796 KiB

long_mansion

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

#define ll long long
#define pii pair<int, int>
#define f first
#define s second

#define pb push_back
#define SZ(x) (int)((x).size())
#define REP1(i,n) for(int i = 1; i<=n;++i)
#define REP(i,n)  for (int i = 0; i<n;++i)

#ifdef BALBIT
#define bug(...) cout<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cout<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&& ...y) {cout<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int inf = 1e9;
const int N = 500005;

int tol[21][N], tor[21][N], need[N], lb[N], rb[N];
int last[N];
vector<int> keys[N];

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    // cout<<"HI";
    // bug("HI"); return 0;
    int n; cin>>n;
    // assert(n<=10);
//    tol[0] = -inf;
    fill(last, last+n+1, -inf);
    REP1(i,n-1) cin>>need[i];
    REP1(i,n) {
        int k; cin>>k;
        REP(j,k) {
            int y; cin>>y; keys[i].pb(y);
            last[y] = i;
        }
        if(i !=n)
            tol[0][i] = last[need[i]];
        else
            tol[0][i] = -inf;
    }
    // return 0;
//    tol[n] = inf;
    fill(last, last+n+1, inf);
    for(int i = n; i>=1; --i) {
        for(int y : keys[i]) last[y] = i;
        if (i!=1)
            tor[0][i] = last[need[i-1]];
        else
            tor[0][i] = inf;
    }
    // return 0;
    REP1(j,20) {
        int df = (1<<(j-1));
        REP1(i,n) {
            tol[j][i] = tol[j-1][i];
            tor[j][i] = tor[j-1][i];
            if(i+df<=n)
                tol[j][i] = min(tol[j][i], tol[j-1][i+df]);
            if(i-df>=1)
                tor[j][i] = max(tor[j][i], tor[j-1][i-df]);
        }
    }
    // return 0;
    // int bigr = 0;
    REP1(i,n) {
        // bug(i);
        if(rb[i-1] >= i) {
            // covered
            int at = i;
            for(int j = 20; j>=0; --j) {
                if(tol[j][at] >= i) {
                    at += (1<<j);
                    
                }
            }
            bug(at);
            if(tor[0][i]<=at) {
                lb[i] = lb[i-1]; rb[i] = rb[i-1];
            }else{
                lb[i] = i; rb[i] = at;
            }
            bug(i, lb[i], rb[i]);
        }else{
            lb[i] = rb[i] = i;
            for(;; ) {
                // grow to the left
                for(int j = 20; j>=0; --j) {
                    if(tor[j][lb[i]] <= rb[i]) {
                        lb[i] -= (1<<j);
                    }
                }
                int tmp = rb[i];
                for(int j = 20; j>=0; --j) {
                    if(tol[j][rb[i]] >= lb[i]) {
                        rb[i] += (1<<j);
                    }
                }
                if(tmp == rb[i]) break;
            }
            bug(i, lb[i], rb[i]);
        }
    }
    // return 0;
    int q; cin>>q;
    while(q--) {
        int x, y; cin>>x>>y;
        // bug(x,lb[x],rb[x],y);
        if(y>=lb[x]&&y<=rb[x]) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
}

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