Submission #516628

#	Time	Username	Problem	Language	Result	Execution time	Memory
516628		K4YAN	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	520 ms	48840 KiB

long_mansion

//Be Name Khoda

#include<bits/stdc++.h>
#pragma GCC optmize("Ofast,unroll-loops")
#pragma GCC target ("avx2,tune=native")

using namespace std;

#define ll long long
#define ld long double
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define plll pair<pll, ll>

const int mxn = 5e5 + 32;
int n, t, k, q;
int c[mxn], cnt[mxn];
pii ans[mxn];
vector<int> keys[mxn];

void input() {

    cin >> n;
    for(int i = 1; i < n; i++) {
        cin >> c[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> k;
        for(int j = 0; j < k; j++) {
            cin >> q;
            keys[i].push_back(q);
        }
    } cin >> t;

}

inline void merge(int l, int r, int m) {

    bool mark[r - l + 5];
    int tmp[r - l + 5];
    int pr = m, pl = m - 1;
    memset(mark, 0, sizeof(mark));
    memset(tmp, 0, sizeof(tmp));

    for(int i = m - 1; i > l - 1; i--) {
        for(auto u : keys[i]) cnt[u]++;
        while(pr < r) {
            if(cnt[c[pr - 1]] <= 0) {
                break;
            }
            if(cnt[c[pr - 1]] > 0) {
                for(auto u : keys[pr]) cnt[u]++;
                pr++;
            } 
        }
        tmp[i - l] = pr;
        if(i > l) {
            if(cnt[c[i - 1]] > 0) mark[i - l] = 1;
        }
    }
    for(int i = l; i < m; i++) {
        if(mark[i - l]) continue;
        if(ans[i].second >= m) {
            ans[i].second = tmp[i - l];
        }
        for(int j = i + 1; j < m; j++) {
            if(!mark[j - l]) break;
            if(ans[j].second < m) continue;
            ans[j].first = i, ans[j].second = tmp[i - l];
        }
    }

    for(int i = l; i < pr; i++) {
        for(auto u : keys[i]) cnt[u]--;
    }
    for(int i = m; i < r; i++) {
        for(auto u : keys[i]) cnt[u]++;
        while(pl > l - 1) {
            if(cnt[c[pl]] <= 0) {
                break;
            }
            if(cnt[c[pl]] > 0) {
                for(auto u : keys[pl]) cnt[u]++;
                pl--;
            }
        }
        tmp[i - l] = pl + 1;
        if(i < r - 1) {
            if(cnt[c[i]] > 0) mark[i - l] = 1;
        }
    }
    for(int i = r - 1; i > m - 1; i--) {
        if(mark[i - l]) continue;
        if(ans[i].first <= m) {
            ans[i].first = tmp[i - l];
        }
        for(int j = i - 1; j > m - 1; j--) {
            if(!mark[j - l]) break;
            if(ans[j].first > m) continue;
            ans[j].first = tmp[i - l], ans[j].second = i + 1;
        }
    }
    for(int i = pl + 1; i < r; i++) {
        for(auto u : keys[i]) cnt[u]--;
    }
    return;

}

void solve(int l, int r) {

    if(r - l <= 0) return;
    if(r - l == 1) {
        ans[l] = make_pair(l, r);
        return;
    }
    int m = (l + r) >> 1;
    solve(l, m); solve(m, r);
    merge(l, r, m);
    return;

}

int main() {

    ios::sync_with_stdio(false); cin.tie(NULL);

    input(), solve(1, n + 1);
    for(int i = 0; i < t; i++) {
        int x, y;
        cin >> x >> y;
        if(y < ans[x].first || ans[x].second <= y) {
            cout << "NO\n";
            continue;
        }
        cout << "YES\n";
    }
    return 0;

}

Compilation message (stderr)

long_mansion.cpp:4: warning: ignoring '#pragma GCC optmize' [-Wunknown-pragmas]
    4 | #pragma GCC optmize("Ofast,unroll-loops")
      |

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