Submission #1270905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270905		chikien2009	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	280 ms	227228 KiB

Main

#include <bits/stdc++.h>

using namespace std;

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

int n, k, m, q, a, b, c, x, y;
pair<int, int> sp1[20][100000], sp2[20][20][100000], temp;
vector<int> s[100000], e[100000];
multiset<int> ms;

inline pair<int, int> Combine(pair<int, int> ina, pair<int, int> inb)
{
    return {min(ina.first, inb.first), max(ina.second, inb.second)};
}

inline pair<int, int> Get(int f, int l, int r)
{
    int len = __lg(r - l + 1);
    return Combine(sp2[f][len][l], sp2[f][len][r - (1 << len) + 1]);
}

int main()
{
    setup();

    cin >> n >> k >> m;
    while (m--)
    {
        cin >> a >> b;
        a--;
        b--;
        if (a < b)
        {
            c = min(a + k - 1, b - 1);
            s[a].push_back(b);
            e[c].push_back(b);
        }
        else
        {
            c = max(b + 1, a - k + 1);
            s[c].push_back(b);
            e[a].push_back(b);
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (auto &j : s[i])
        {
            ms.insert(j);
        }
        sp1[0][i] = {i, i};
        if (!ms.empty())
        {
            sp1[0][i] = {min(i, (*ms.begin())), max(i, (*ms.rbegin()))};
        }
        sp2[0][0][i] = sp1[0][i];
        for (auto &j : e[i])
        {
            ms.erase(ms.lower_bound(j));
        }
    }
    for (int i = 1; i <= __lg(n); ++i)
    {
        for (int j = 0; j + (1 << i) <= n; ++j)
        {
            sp2[0][i][j] = Combine(sp2[0][i - 1][j], sp2[0][i - 1][j + (1 << (i - 1))]);
        }
    }
    for (int i = 1; i <= __lg(n); ++i)
    {
        for (int j = 0; j <= __lg(n); ++j)
        {
            for (int h = 0; h + (1 << j) <= n; ++h)
            {
                sp2[i][j][h] = Get(i - 1, sp2[i - 1][j][h].first, sp2[i - 1][j][h].second);
            }
        }
    }
    // for (int i = 0; i <= __lg(n); ++i)
    // {
    //     for (int j = 0; j <= __lg(n); ++j)
    //     {
    //         for (int k = 0; k + (1 << j) <= n; ++k)
    //         {
    //             cout << i << " " << j << " " << k << " " << sp2[i][j][k].first << " " << sp2[i][j][k].second << "\n";
    //         }
    //     }
    // }
    cin >> q;
    while (q--)
    {
        cin >> a >> b;
        a--;
        b--;
        x = y = a;
        c = 0;
        for (int i = __lg(n); i >= 0; --i)
        {
            temp = Get(i, x, y);
            if (b < temp.first || temp.second < b)
            {
                x = temp.first;
                y = temp.second;
                c += (1 << i);
            }
        }
        temp = Get(0, x, y);
        if (temp.first <= b && b <= temp.second)
        {
            cout << c + 1 << "\n";
        }
        else
        {
            cout << -1 << "\n";
        }
    }
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13