Submission #986061

#	Time	Username	Problem	Language	Result	Execution time	Memory
986061		KLKLK	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	309 ms	52396 KiB

Main

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>

#define PI pair<int, int>

using namespace std;

struct SegmentTree
{
    int n;
    vector<PI> data;

    void combine(int v)
    {
        data[v].first = min(data[v << 1].first, data[v << 1 | 1].first);
        data[v].second = max(data[v << 1].second, data[v << 1 | 1].second);
    }

    SegmentTree(int n) : n(n), data(vector<PI>(n << 1, {INT32_MAX, INT32_MIN}))
    {

    }

    void build(int l, const vector<PI> &I)
    {
        for (int i = 1; i <= l; ++i) data[n + i] = I[i];
        for (int v = n - 1; v; --v) combine(v);
    }

    PI query(int l, int r)
    {
        l += n;
        r += n;

        PI ans = {INT32_MAX, INT32_MIN};
        while (l < r)
        {
            if (l & 1)
            {
                ans = {min(ans.first, data[l].first), max(ans.second, data[l].second)};
                l++;
            }
            if (r & 1)
            {
                --r;
                ans = {min(ans.first, data[r].first), max(ans.second, data[r].second)};
            }
            l >>= 1;
            r >>= 1;
        }

        return ans;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, q, k;
    cin >> n >> k >> m;

    vector<PI> forward;
    vector<PI> backward;

    int a, b;
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b;
        if (a < b)
        {
            forward.emplace_back(a, b);
            forward.emplace_back(min(a + k, b), -b);
        }
        else
        {
            backward.emplace_back(a, b);
            backward.emplace_back(max(a - k, b), -b);
        }
    }

    multiset<int> ends;
    vector<PI> I(n + 1);
    sort(forward.begin(), forward.end());
    sort(backward.begin(), backward.end(), greater<>());

    auto itr = forward.begin();
    for (int i = 1; i <= n; ++i)
    {
        while (itr != forward.end() && itr->first == i)
        {
            if (itr->second > 0) ends.insert(itr->second);
            else ends.erase(ends.find(-itr->second));
            ++itr;
        }

        if (!ends.empty()) I[i].second = *ends.rbegin();
        else I[i].second = i;
    }
    
    itr = backward.begin();
    for (int i = n; i; --i)
    {
        while (itr != backward.end() && itr->first == i)
        {
            if (itr->second > 0) ends.insert(itr->second);
            else ends.erase(ends.find(-itr->second));
            ++itr;
        }

        if (!ends.empty()) I[i].first = *ends.begin();
        else I[i].first = i;
    }

    vector<SegmentTree> interval(20, SegmentTree(1 << 17));
    interval[0].build(n, I);

    for (int j = 1; j < 20; ++j)
    {
        for (int i = 1; i <= n; ++i)
        {
            I[i] = interval[j - 1].query(I[i].first, I[i].second + 1);
        }
        interval[j].build(n, I);
    }

    cin >> q;
    while (q--)
    {
        cin >> a >> b;
        if (b < interval[19].query(a, a + 1).first || b > interval[19].query(a, a + 1).second) cout << "-1\n";
        else
        {
            int res = 1;
            int l = a;
            int r = a;
            for (int j = 19; j >= 0; -- j)
            {
                PI qry = interval[j].query(l, r + 1);
                if (b < qry.first || b > qry.second)
                {
                    res += 1 << j;
                    l = qry.first;
                    r = qry.second;
                }
            }
            cout << res << "\n";
        }
    }
}

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