oj.uz

Submission #358863

# Submission time Handle Problem Language Result Execution time Memory
358863 2021-01-26T06:54:21 Z ijxjdjd Long Mansion (JOI17_long_mansion) C++14
0 / 100
 3000 ms 15624 KB 
#include <bits/stdc++.h>
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;
const int MAXN = (int)(5e5) + 5;
int maxright[MAXN];
int to[MAXN];
int last[MAXN];
vector<int> has[MAXN];
pair<int, int> interval[MAXN];
bool cont(int l, int r, int k) {
    if (has[k].size() == 0 || has[k][0] > r || has[k].back() < l || k < 0) {
        return false;
    }
    else {
        int low = 0;
        int high = has[k].size()-1;
        while (low < high) {
            int mid = (low + high)/2;
            if (has[k][mid] >= l) {
                high = mid;
            }
            else {
                low = mid+1;
            }
        }
        int sh = high;
        low = 0; high = has[k].size()-1;
        while (low < high) {
            int mid = (low + high+1)/2;
            if (has[k][mid] <= r) {
                low = mid;
            }
            else {
                high = mid-1;
            }
        }
        return (low - sh + 1) > 0;
    }
}
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, Q;
	cin >> N;
	to[N] = -1;
	FR(i, N-1) {
        cin >> to[i];
        to[i]--;
	}
	FR(i, N) {
        int B;
        cin >> B;
        FR(j, B) {
            int a;
            cin >> a;
            a--;
            has[a].push_back(i);
        }
	}
	maxright[N-1] = N-1;
	for (int i = N-2; i >= 0; i--) {
        int u = i;
        while (cont(i, u, to[u])) {
            u = maxright[u+1];
        }
        maxright[i] = u;
	}
	for (int i = 0; i < N; i++) {
        int l = i;
        int r = i;
        while (true) {
            if (l != 0 && cont(l, r, to[l-1])) {
                l = interval[l-1].first;
//                r = max(r, interval[l-1].second);
            }
            else if (r != N-1 && cont(l, r, to[r])) {
                r++;
            }
            else {
                break;
            }
        }
        interval[i] = {l, r};
	}
	cin >> Q;
	FR(i, Q) {
        int x, y;
        cin >> x >> y;
        x--, y--;
        if (interval[x].first <= y && y <= interval[x].second) {
            cout << "YES" << '\n';
        }
        else cout << "NO" << '\n';
    }
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12268 KB Output is correct
2 Correct 102 ms 12268 KB Output is correct
3 Correct 497 ms 12524 KB Output is correct
4 Correct 12 ms 12140 KB Output is correct
5 Execution timed out 3082 ms 12140 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12268 KB Output is correct
2 Correct 102 ms 12268 KB Output is correct
3 Correct 497 ms 12524 KB Output is correct
4 Correct 12 ms 12140 KB Output is correct
5 Execution timed out 3082 ms 12140 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 15624 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12268 KB Output is correct
2 Correct 102 ms 12268 KB Output is correct
3 Correct 497 ms 12524 KB Output is correct
4 Correct 12 ms 12140 KB Output is correct
5 Execution timed out 3082 ms 12140 KB Time limit exceeded
6 Halted 0 ms 0 KB -