Submission #1033110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033110		borisAngelov	Long Mansion (JOI17_long_mansion)	C++17	100 / 100	232 ms	43088 KiB

long_mansion

#include <bits/stdc++.h>

using namespace std;

const int maxn = 500005;

int n, q;
int a[maxn];

int l[maxn];
int r[maxn];

vector<int> keysPos[maxn];

bool isPossible(int leftPos, int rightPos, int key)
{
    if (keysPos[key].empty()) return false;
    int pos = lower_bound(keysPos[key].begin(), keysPos[key].end(), leftPos) - keysPos[key].begin();
    return pos < keysPos[key].size() && keysPos[key][pos] <= rightPos;
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n - 1; ++i)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= n; ++i)
    {
        int cnt;
        cin >> cnt;

        for (int j = 1; j <= cnt; ++j)
        {
            int key;
            cin >> key;
            keysPos[key].push_back(i);
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        l[i] = r[i] = i;

        //cout << "on " << i << endl;

        while (true)
        {
            //cout << "left " << isPossible(l[i], r[i], a[l[i] - 1]) << "\n";

            if (l[i] > 1 && isPossible(l[i], r[i], a[l[i] - 1]) == true)
            {
                r[i] = max(r[i], r[l[i] - 1]);
                l[i] = l[l[i] - 1];
            }
            else if (r[i] < n && isPossible(l[i], r[i], a[r[i]]) == true)
            {
                ++r[i];
            }
            else
            {
                break;
            }
        }

        //cout << i << " -> " << l[i] << " " << r[i] << endl;
    }

    cin >> q;

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

        if (l[x] <= y && y <= r[x])
        {
            cout << "YES\n";
        }
        else
        {
            cout << "NO\n";
        }
    }

    return 0;
}

Compilation message (stderr)

long_mansion.cpp: In function 'bool isPossible(int, int, int)':
long_mansion.cpp:19:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     return pos < keysPos[key].size() && keysPos[key][pos] <= rightPos;
      |            ~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75