Submission #1264123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264123		aihoi	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	244 ms	67640 KiB

long_mansion

#include<bits/stdc++.h>
#include<algorithm>
#include<random>
#include<chrono>
#include<cstdlib>
#include<ctime>
#include<numeric>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<queue>
#include<iomanip>
#define int long long
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,int>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
using namespace std;

const int NMAX = 500000 + 5;

int n, q;
int c[NMAX];
vector<int> arr[NMAX];    // keys in each room (like a[i])
vector<int> pos[NMAX];    // positions (rooms) that contain key type t
int lef[NMAX], rig[NMAX];
int X[NMAX], Y[NMAX];

bool inside(int l, int r, int key){
    if (key <= 0 || key >= NMAX) return false;
    auto &v = pos[key];
    if (v.empty()) return false;
    auto it = lower_bound(v.begin(), v.end(), l);
    return it != v.end() && *it <= r;
}

void input(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n)) exit(0);
    FOR(i,1,n-1) cin >> c[i];
    FOR(i,1,n){
        int b; cin >> b;
        arr[i].resize(b);
        FOR(j,0,b-1){
            cin >> arr[i][j];
            // push room index i into pos[key], we iterate i increasing so pos[key] stays sorted
            if (arr[i][j] > 0 && arr[i][j] < NMAX) pos[ arr[i][j] ].push_back(i);
        }
    }
    cin >> q;
    FOR(i,1,q) cin >> X[i] >> Y[i];
}

void solve(){
    // compute lef/rig for each starting room i
    FOR(i,1,n){
        lef[i] = rig[i] = i;
        bool nxt = true;
        while (nxt){
            nxt = false;
            // try expand left using merge with precomputed block if corridor c[lef[i]-1] is present in current [lef,rig]
            if (lef[i] > 1 && inside(lef[i], rig[i], c[lef[i]-1])){
                // merge with block of lef[i]-1 (which has been computed because lef[i]-1 < i)
                rig[i] = max(rig[i], rig[lef[i]-1]);
                lef[i] = lef[lef[i]-1];
                nxt = true;
                continue; // after merging left, try again from top
            }
            // else try expand right by checking corridor c[rig[i]]
            if (rig[i] < n && inside(lef[i], rig[i], c[rig[i]])){
                rig[i]++; // include the next room on right
                nxt = true;
                // note: after rig[i]++ we don't immediately merge with precomputed blocks to keep same logic as original;
                // on next outer loop iteration we may merge via lef[rig[i]] if applicable.
            }
        }
    }

    // answer queries
    FOR(i,1,q){
        int x = X[i], y = Y[i];
        bool ok = (lef[x] <= y && y <= rig[x]);
        cout << (ok ? "YES" : "NO") << '\n';
    }
}

signed main(){
    input();
    solve();
    return 0;
}

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