제출 #717191

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
717191		fatemetmhr	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	479 ms	66684 KiB

long_mansion

// ~ Be Name Khoda ~

#include <bits/stdc++.h>
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e6   + 10;
const int maxnt =  4e6   + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   +  7;
const ll  inf   =  1e18;

int n, c[maxn5], nxt[maxn5], pre[maxn5];
int l[maxn5], r[maxn5], last[maxn5];
vector <int> av[maxn5], good;
pair <int, int> mn[maxnt];

void upd(int l, int r, int id, int val, int v){
    if(r - l == 1){
        mn[v] = {val, id};
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid)
        upd(l, mid, id, val, v * 2);
    else
        upd(mid, r, id, val, v * 2 + 1);
    mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
}

int get_first(int l, int r, int lq, int rq, int val, int v){
    if(rq <= l || r <= lq || mn[v].fi > val)
        return n;
    if(r - l == 1)
        return l;
    int mid = (l + r) >> 1;
    int ans = get_first(l, mid, lq, rq, val, v * 2);
    if(ans >= n)
        ans = get_first(mid, r, lq, rq, val, v * 2 + 1);
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n;
    for(int i = 0; i < n - 1; i++)
        cin >> c[i];
    memset(last, -1, sizeof last);
    for(int i = 0; i < n; i++){
        int b; cin >> b;
        while(b--){
            int a; cin >> a;
            av[i].pb(a);
            last[a] = i;
        }
        if(i < n - 1)
            pre[i] = last[c[i]];
    }
    fill(last, last + n + 5, n);
    for(int i = n - 1; i; i--){
        for(auto u : av[i])
            last[u] = i;
        nxt[i - 1] = last[c[i - 1]];       
    }
    fill(r, r + n + 5, n - 1);
    for(int i = 0; i < n - 1; i++)
        upd(0, n, i, pre[i], 1);
    upd(0, n, n - 1, -1, 1);
    good.pb(-1);
    int curr = get_first(0, n, 0, n, -1, 1);
    for(int i = 0; i < n; i++){
        l[i] = good.back() + 1;
        r[i] = curr;
        //cout << "ok " << i << ' ' << l[i] << ' ' << r[i] << ' ' << pre[i] << ' ' << nxt[i] << '\n';
        if(i == n - 1)
            break;
        upd(0, n, i, n + 5, 1);
        while(true){
            if(good.back() == -1){
                curr = get_first(0, n, 0, n, -1, 1);
                break;
            }
            int ind = get_first(0, n, 0, nxt[good.back()], good.back(), 1);
            if(ind < n){
                curr = ind;
                break;
            }
            good.pop_back();
        }
        int ind = get_first(0, n, 0, nxt[i], i, 1);
        //cout << "here " << i << ' ' << ind << '\n';
        if(ind < n){
            good.pb(i);
            curr = ind;
        }
    }

    int q; cin >> q;
    while(q--){
        int x, y; cin >> x >> y;
        x--; y--;
        cout << (l[x] <= y && y <= r[x] ? "YES" : "NO") << '\n';
    }
}

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