Submission #69926

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
69926	2018-08-22T03:14:40 Z	MatheusLealV	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	608 ms	68888 KB

long_mansion

#include <bits/stdc++.h>
#define N 500050
using namespace std;

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

int e[N];

vector<int> pos[N], T[N];

void solve(int l, int r, int i)
{
    while(true)
    {
        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) r = max(r + 1, e[r]), ok = 1;//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) l = min(l - 1, L[l]), ok = 1;;//solve(min(l - 1, L[l]), r, i);        
        }

        if(!ok) break;
    }
}

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);

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

    for(int i = n; i >= 1; i--)
    {
    	e[i] = i;

    	for(auto x: T[i])
    	{
    		if(x == c[i])
    		{
    			e[i] = e[i + 1];

    			while(e[i] <= n)
    			{
           			 int q = upper_bound(pos[c[e[i]]].begin(), pos[c[e[i]]].end(), e[i]) - lower_bound(pos[c[e[i]]].begin(), pos[c[e[i]]].end(), i);

           			 if(q) e[i] = e[e[i] + 1];

           			 else break;
    			}

    			break;
    		}
    	}
 
    }

    for(int i = 1; i <= n; i++)
    {
        if(L[i - 1] <= i and i <= R[i - 1])
        {
            int q = upper_bound(pos[c[i - 1]].begin(), pos[c[i - 1]].end(), e[i]) - lower_bound(pos[c[i - 1]].begin(), pos[c[i - 1]].end(), i);

            if(q) L[i] = L[i - 1], R[i] = max(R[i - 1], e[i]);

            else L[i] = i, R[i] = e[i];
        }

       else 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	28 ms	24056 KB	Output is correct
2	Correct	27 ms	24056 KB	Output is correct
3	Correct	35 ms	24236 KB	Output is correct
4	Correct	32 ms	24236 KB	Output is correct
5	Correct	30 ms	24236 KB	Output is correct
6	Correct	24 ms	24236 KB	Output is correct
7	Correct	29 ms	24240 KB	Output is correct

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	24056 KB	Output is correct
2	Correct	27 ms	24056 KB	Output is correct
3	Correct	35 ms	24236 KB	Output is correct
4	Correct	32 ms	24236 KB	Output is correct
5	Correct	30 ms	24236 KB	Output is correct
6	Correct	24 ms	24236 KB	Output is correct
7	Correct	29 ms	24240 KB	Output is correct
8	Correct	173 ms	25720 KB	Output is correct
9	Correct	151 ms	27584 KB	Output is correct
10	Correct	159 ms	27832 KB	Output is correct
11	Correct	161 ms	27908 KB	Output is correct
12	Correct	132 ms	27908 KB	Output is correct
13	Correct	140 ms	27908 KB	Output is correct
14	Correct	189 ms	27908 KB	Output is correct
15	Correct	152 ms	27908 KB	Output is correct
16	Correct	152 ms	28032 KB	Output is correct
17	Correct	132 ms	28032 KB	Output is correct
18	Correct	160 ms	28032 KB	Output is correct
19	Correct	137 ms	28032 KB	Output is correct
20	Correct	152 ms	28032 KB	Output is correct
21	Correct	158 ms	28032 KB	Output is correct
22	Correct	151 ms	28032 KB	Output is correct
23	Correct	200 ms	28032 KB	Output is correct
24	Correct	161 ms	28032 KB	Output is correct
25	Correct	137 ms	28032 KB	Output is correct
26	Correct	145 ms	28032 KB	Output is correct

Subtask #3
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	439 ms	34872 KB	Output is correct
2	Correct	415 ms	34872 KB	Output is correct
3	Correct	329 ms	34872 KB	Output is correct
4	Correct	434 ms	34900 KB	Output is correct
5	Correct	365 ms	34900 KB	Output is correct
6	Correct	283 ms	34900 KB	Output is correct
7	Correct	244 ms	34900 KB	Output is correct
8	Correct	231 ms	34900 KB	Output is correct
9	Correct	261 ms	34900 KB	Output is correct
10	Correct	273 ms	34900 KB	Output is correct
11	Correct	253 ms	34900 KB	Output is correct

Subtask #4
75.0 / 75.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	24056 KB	Output is correct
2	Correct	27 ms	24056 KB	Output is correct
3	Correct	35 ms	24236 KB	Output is correct
4	Correct	32 ms	24236 KB	Output is correct
5	Correct	30 ms	24236 KB	Output is correct
6	Correct	24 ms	24236 KB	Output is correct
7	Correct	29 ms	24240 KB	Output is correct
8	Correct	173 ms	25720 KB	Output is correct
9	Correct	151 ms	27584 KB	Output is correct
10	Correct	159 ms	27832 KB	Output is correct
11	Correct	161 ms	27908 KB	Output is correct
12	Correct	132 ms	27908 KB	Output is correct
13	Correct	140 ms	27908 KB	Output is correct
14	Correct	189 ms	27908 KB	Output is correct
15	Correct	152 ms	27908 KB	Output is correct
16	Correct	152 ms	28032 KB	Output is correct
17	Correct	132 ms	28032 KB	Output is correct
18	Correct	160 ms	28032 KB	Output is correct
19	Correct	137 ms	28032 KB	Output is correct
20	Correct	152 ms	28032 KB	Output is correct
21	Correct	158 ms	28032 KB	Output is correct
22	Correct	151 ms	28032 KB	Output is correct
23	Correct	200 ms	28032 KB	Output is correct
24	Correct	161 ms	28032 KB	Output is correct
25	Correct	137 ms	28032 KB	Output is correct
26	Correct	145 ms	28032 KB	Output is correct
27	Correct	439 ms	34872 KB	Output is correct
28	Correct	415 ms	34872 KB	Output is correct
29	Correct	329 ms	34872 KB	Output is correct
30	Correct	434 ms	34900 KB	Output is correct
31	Correct	365 ms	34900 KB	Output is correct
32	Correct	283 ms	34900 KB	Output is correct
33	Correct	244 ms	34900 KB	Output is correct
34	Correct	231 ms	34900 KB	Output is correct
35	Correct	261 ms	34900 KB	Output is correct
36	Correct	273 ms	34900 KB	Output is correct
37	Correct	253 ms	34900 KB	Output is correct
38	Correct	564 ms	49316 KB	Output is correct
39	Correct	485 ms	53664 KB	Output is correct
40	Correct	439 ms	53664 KB	Output is correct
41	Correct	608 ms	53664 KB	Output is correct
42	Correct	253 ms	53664 KB	Output is correct
43	Correct	258 ms	53664 KB	Output is correct
44	Correct	416 ms	53664 KB	Output is correct
45	Correct	380 ms	53664 KB	Output is correct
46	Correct	489 ms	53664 KB	Output is correct
47	Correct	325 ms	53664 KB	Output is correct
48	Correct	307 ms	53664 KB	Output is correct
49	Correct	482 ms	53664 KB	Output is correct
50	Correct	409 ms	53664 KB	Output is correct
51	Correct	526 ms	53664 KB	Output is correct
52	Correct	329 ms	53664 KB	Output is correct
53	Correct	390 ms	60984 KB	Output is correct
54	Correct	604 ms	68888 KB	Output is correct
55	Correct	534 ms	68888 KB	Output is correct

Submission #69926

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 15.0 / 15.0

Subtask #4 75.0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
15.0 / 15.0

Subtask #4
75.0 / 75.0