Submission #1315378

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315378		vuviet	Passport (JOI23_passport)	C++20	0 / 100	2111 ms	558168 KiB

passport

/**
 *     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 = 19;
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];
}

long long cost(int x)
{
    int s = stl[x][0][0], t = str[x][0][0];
    long long 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 += (1ll << 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 x;
        cin >> x;
        cout << cost(x) << "\n";
    }
}

int main()
{
    ReadData();
    Solve();
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46