oj.uz

Submission #69914

# Submission time Handle Problem Language Result Execution time Memory
69914 2018-08-22T00:37:48 Z MatheusLealV Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 17356 KB 
#include <bits/stdc++.h>
#define N 500050
using namespace std;

int n, q, c[N], L[N], R[N];

vector<int> pos[N];

void solve(int l, int r, int i)
{
	L[i] = l;

	R[i] = r;

	bool ok = false;

	if(r < n)
	{
		int q = upper_bound(pos[c[r]].begin(), pos[c[r]].end(), r) - lower_bound(pos[c[r]].begin(), pos[c[r]].end(), l);
		
		if(q) solve(l, max(r + 1, R[r]), i), ok = 1;
	}

	if(l > 1 and !ok)
	{
		int q = upper_bound(pos[c[l - 1]].begin(), pos[c[l - 1]].end(), r) - lower_bound(pos[c[l - 1]].begin(), pos[c[l - 1]].end(), l);

		if(q) solve(min(l - 1, L[l]), r, i);		
	}
}

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

	cin>>n;

	for(int i = 1; i < n; i++) cin>>c[i];

	for(int i = 1; i <= n; i++)
	{
		L[i] = R[i] = i;

		int a, b;

		cin>>a;

		for(int x = 1; x <= a; x++)
		{
			cin>>b;

			pos[b].push_back(i);
		}
	}

	for(int i = 1; i <= n; i++)
	{
		solve(i, i, i);
	}

	cin>>q;

	for(int i = 1; i <= q; i++)
	{
		int x, y;

		cin>>x>>y;

		if(L[x] <= y and y <= R[x]) cout<<"YES\n";

		else cout<<"NO\n";
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12152 KB Output is correct
2 Correct 141 ms 12380 KB Output is correct
3 Correct 580 ms 12584 KB Output is correct
4 Correct 16 ms 12616 KB Output is correct
5 Correct 135 ms 12868 KB Output is correct
6 Correct 22 ms 12936 KB Output is correct
7 Correct 21 ms 12936 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12152 KB Output is correct
2 Correct 141 ms 12380 KB Output is correct
3 Correct 580 ms 12584 KB Output is correct
4 Correct 16 ms 12616 KB Output is correct
5 Correct 135 ms 12868 KB Output is correct
6 Correct 22 ms 12936 KB Output is correct
7 Correct 21 ms 12936 KB Output is correct
8 Correct 168 ms 15276 KB Output is correct
9 Correct 155 ms 15276 KB Output is correct
10 Correct 262 ms 15388 KB Output is correct
11 Correct 695 ms 15516 KB Output is correct
12 Correct 163 ms 15564 KB Output is correct
13 Correct 129 ms 15564 KB Output is correct
14 Correct 144 ms 15564 KB Output is correct
15 Correct 165 ms 15564 KB Output is correct
16 Correct 253 ms 15692 KB Output is correct
17 Correct 123 ms 15692 KB Output is correct
18 Correct 146 ms 15692 KB Output is correct
19 Correct 125 ms 15692 KB Output is correct
20 Correct 226 ms 15692 KB Output is correct
21 Correct 251 ms 15756 KB Output is correct
22 Correct 144 ms 15756 KB Output is correct
23 Correct 127 ms 15756 KB Output is correct
24 Correct 129 ms 15756 KB Output is correct
25 Correct 138 ms 15756 KB Output is correct
26 Correct 135 ms 15756 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 12152 KB Output is correct
2 Correct 141 ms 12380 KB Output is correct
3 Correct 580 ms 12584 KB Output is correct
4 Correct 16 ms 12616 KB Output is correct
5 Correct 135 ms 12868 KB Output is correct
6 Correct 22 ms 12936 KB Output is correct
7 Correct 21 ms 12936 KB Output is correct
8 Correct 168 ms 15276 KB Output is correct
9 Correct 155 ms 15276 KB Output is correct
10 Correct 262 ms 15388 KB Output is correct
11 Correct 695 ms 15516 KB Output is correct
12 Correct 163 ms 15564 KB Output is correct
13 Correct 129 ms 15564 KB Output is correct
14 Correct 144 ms 15564 KB Output is correct
15 Correct 165 ms 15564 KB Output is correct
16 Correct 253 ms 15692 KB Output is correct
17 Correct 123 ms 15692 KB Output is correct
18 Correct 146 ms 15692 KB Output is correct
19 Correct 125 ms 15692 KB Output is correct
20 Correct 226 ms 15692 KB Output is correct
21 Correct 251 ms 15756 KB Output is correct
22 Correct 144 ms 15756 KB Output is correct
23 Correct 127 ms 15756 KB Output is correct
24 Correct 129 ms 15756 KB Output is correct
25 Correct 138 ms 15756 KB Output is correct
26 Correct 135 ms 15756 KB Output is correct
27 Execution timed out 3048 ms 17356 KB Time limit exceeded
28 Halted 0 ms 0 KB -