oj.uz

Submission #69919

# Submission time Handle Problem Language Result Execution time Memory
69919 2018-08-22T02:39:06 Z MatheusLealV Long Mansion (JOI17_long_mansion) C++17
10 / 100
 3000 ms 18804 KB 
#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];

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, R[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);
        }
    }

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

            if(q)  e[i] = j;

            else 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 16 ms 12156 KB Output is correct
2 Correct 136 ms 12468 KB Output is correct
3 Correct 566 ms 12528 KB Output is correct
4 Correct 19 ms 12528 KB Output is correct
5 Correct 146 ms 12580 KB Output is correct
6 Correct 19 ms 12732 KB Output is correct
7 Correct 18 ms 12884 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12156 KB Output is correct
2 Correct 136 ms 12468 KB Output is correct
3 Correct 566 ms 12528 KB Output is correct
4 Correct 19 ms 12528 KB Output is correct
5 Correct 146 ms 12580 KB Output is correct
6 Correct 19 ms 12732 KB Output is correct
7 Correct 18 ms 12884 KB Output is correct
8 Correct 156 ms 16436 KB Output is correct
9 Correct 128 ms 16436 KB Output is correct
10 Correct 243 ms 16468 KB Output is correct
11 Correct 674 ms 16584 KB Output is correct
12 Correct 194 ms 16596 KB Output is correct
13 Correct 159 ms 16596 KB Output is correct
14 Correct 145 ms 16596 KB Output is correct
15 Correct 132 ms 16620 KB Output is correct
16 Correct 244 ms 16876 KB Output is correct
17 Correct 158 ms 16876 KB Output is correct
18 Correct 181 ms 16876 KB Output is correct
19 Correct 162 ms 16876 KB Output is correct
20 Correct 174 ms 16876 KB Output is correct
21 Correct 321 ms 16880 KB Output is correct
22 Correct 164 ms 16880 KB Output is correct
23 Correct 141 ms 16880 KB Output is correct
24 Correct 161 ms 16880 KB Output is correct
25 Correct 167 ms 16880 KB Output is correct
26 Correct 157 ms 16880 KB Output is correct

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 12156 KB Output is correct
2 Correct 136 ms 12468 KB Output is correct
3 Correct 566 ms 12528 KB Output is correct
4 Correct 19 ms 12528 KB Output is correct
5 Correct 146 ms 12580 KB Output is correct
6 Correct 19 ms 12732 KB Output is correct
7 Correct 18 ms 12884 KB Output is correct
8 Correct 156 ms 16436 KB Output is correct
9 Correct 128 ms 16436 KB Output is correct
10 Correct 243 ms 16468 KB Output is correct
11 Correct 674 ms 16584 KB Output is correct
12 Correct 194 ms 16596 KB Output is correct
13 Correct 159 ms 16596 KB Output is correct
14 Correct 145 ms 16596 KB Output is correct
15 Correct 132 ms 16620 KB Output is correct
16 Correct 244 ms 16876 KB Output is correct
17 Correct 158 ms 16876 KB Output is correct
18 Correct 181 ms 16876 KB Output is correct
19 Correct 162 ms 16876 KB Output is correct
20 Correct 174 ms 16876 KB Output is correct
21 Correct 321 ms 16880 KB Output is correct
22 Correct 164 ms 16880 KB Output is correct
23 Correct 141 ms 16880 KB Output is correct
24 Correct 161 ms 16880 KB Output is correct
25 Correct 167 ms 16880 KB Output is correct
26 Correct 157 ms 16880 KB Output is correct
27 Execution timed out 3047 ms 18804 KB Time limit exceeded
28 Halted 0 ms 0 KB -