Submission #1315388

#TimeUsernameProblemLanguageResultExecution timeMemory
1315388vuvietPassport (JOI23_passport)C++20
0 / 100
2090 ms501400 KiB
/**
 *     Author:       trviet
 *     Studies at:   Le Hong Phong High School for the Gifted
**/

#include <bits/stdc++.h>

using namespace std;

constexpr int N = 2e5 + 5, Log = 18;
int n, q, lg2[N], l[N], r[N], x[N], y[N];
int stl[N][Log][Log], str[N][Log][Log];

int minquery(int k, int s, int t)
{
    int j = lg2[t - s + 1];
    return min(stl[s][j][k], stl[t - (1 << j) + 1][j][k]);
}

int maxquery(int k, int s, int t)
{
    int j = lg2[t - s + 1];
    return max(str[s][j][k], str[t - (1 << j) + 1][j][k]);
}

void BuildSparse(int k)
{
    for (int i = 1; i <= n; ++i)
        stl[i][0][k] = x[i], str[i][0][k] = y[i];
    for (int j = 1; j < Log; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
        {
            stl[i][j][k] = min(stl[i][j - 1][k], stl[i + (1 << (j - 1))][j - 1][k]);
            str[i][j][k] = max(str[i][j - 1][k], str[i + (1 << (j - 1))][j - 1][k]);
        }
}

void Init()
{
    lg2[1] = 0;
    for (int i = 2; i < N; i++)
        lg2[i] = lg2[i / 2] + 1;
}

void ReadData()
{
    cin.tie(0)->sync_with_stdio(0);
    Init();
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> l[i] >> r[i];
}

int cost(int x)
{
    int s = stl[x][0][0], t = str[x][0][0], res = 1;
    if (s == 1 && t == n) return res;
    for (int k = Log - 1; k >= 0; --k)
    {
        int i = minquery(k, s, t), j = maxquery(k, s, t);
        if (i > 1 || j < n) {
            res += (1 << k), s = i, t = j;
        }
    }
    int i = minquery(0, s, t), j = maxquery(0, s, t);
    return (i <= 1 && j >= n ? res + 1 : -1);
}

void Solve()
{
    for (int i = 1; i <= n; ++i)
        x[i] = l[i], y[i] = r[i];
    BuildSparse(0);
    for (int k = 1; k < Log; ++k)
    {
        for (int i = 1; i <= n; ++i)
        {
            int s = stl[i][0][k - 1], t = str[i][0][k - 1];
            x[i] = minquery(k - 1, s, t), y[i] = maxquery(k - 1, s, t);
        }
        BuildSparse(k);
    }
    cin >> q;
    while (q-- > 0)
    {
        int st;
        cin >> st;
        cout << cost(st) << "\n";
    }
}

int main()
{
    ReadData();
    Solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...