Submission #1119812

#TimeUsernameProblemLanguageResultExecution timeMemory
1119812Neco_arcLong Mansion (JOI17_long_mansion)C++17
10 / 100
3037 ms18816 KiB
#include <bits/stdc++.h>

#define ll long long
#define name "Long Mansion"
#define all(x) x.begin(), x.end()
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define fi(i, a, b)  for(int i = a; i <= b; ++i)
#define fid(i, a, b) for(int i = a; i >= b; --i)
#define maxn (int) (5e5 + 7)

using namespace std;

/// ma

int n;
vector<int> P[maxn];
int a[maxn], fl[maxn], fr[maxn];

int check(int l, int r, int x) {
    auto it = lower_bound(all(P[x]), l);
    return it != P[x].end() && (*it <= r);
}

void solve() {

    cin >> n;
    fi(i, 1, n - 1) cin >> a[i];
    fi(i, 1, n) {
        int sz, x; cin >> sz;
        while(sz--) cin >> x, P[x].push_back(i);
    }

    fi(i, 1, n) {
        int l = i, r = i, ok = 1;
        while(ok) {
            ok = 0;

            if(l > 1 && check(l, r, a[l - 1])) {
                ok = 1;
                l = fl[l - 1], r = max(r, fr[l]);
            }
            else if(r < n && check(l, r, a[r])) { ++r, ok = 1; }
        }
        fl[i] = l, fr[i] = r;
    }

    int q; cin >> q;
    fi(i, 1, q) {
        int x, y; cin >> x >> y;
        if(fl[x] <= y && y <= fr[x]) cout << "YES\n";
        else cout << "NO\n";
    }

}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    if(fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }

    solve();

}

Compilation message (stderr)

long_mansion.cpp: In function 'int main()':
long_mansion.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
long_mansion.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...