oj.uz

Submission #69922

# Submission time Handle Problem Language Result Execution time Memory
69922 2018-08-22T03:01:12 Z MatheusLealV Long Mansion (JOI17_long_mansion) C++17
0 / 100
 3000 ms 31612 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], 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, 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);

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

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

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

    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24020 KB Output is correct
2 Incorrect 93 ms 24352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24020 KB Output is correct
2 Incorrect 93 ms 24352 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

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

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24020 KB Output is correct
2 Incorrect 93 ms 24352 KB Output isn't correct
3 Halted 0 ms 0 KB -