Submission #751379

#	Time	Username	Problem	Language	Result	Execution time	Memory
751379		Kihihihi	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	710 ms	119592 KiB

Main

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <cassert>
#include <ctime>
#include <chrono>
#include <cstdio>
#include <random>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <deque>
#include <queue>
#include <bitset>
#include <list>
#include <fstream>
#include <functional>
#include <complex>
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

short skip_cin = 0;
const long long INF = 1e9, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 18;
const long double EPS = 1e-9, PI = acos(-1);

struct quemin
{
    deque<pair<long long, long long>> d;
    long long l, r;

    quemin()
    {
        l = 0;
        r = -1;
    }

    void push_back(long long val)
    {
        r++;
        while (d.size() && d.back().first >= val)
        {
            d.pop_back();
        }
        d.push_back({ val, r });
    }

    void pop_front()
    {
        if (d.front().second == l)
        {
            d.pop_front();
        }
        l++;
    }

    long long get_min()
    {
        return d.front().first;
    }
};

struct quemax
{
    deque<pair<long long, long long>> d;
    long long l, r;

    quemax()
    {
        l = 0;
        r = -1;
    }

    void push_back(long long val)
    {
        r++;
        while (d.size() && d.back().first <= val)
        {
            d.pop_back();
        }
        d.push_back({ val, r });
    }

    void pop_front()
    {
        if (d.front().second == l)
        {
            d.pop_front();
        }
        l++;
    }

    long long get_max()
    {
        return d.front().first;
    }
};

struct segtree
{
    long long n;
    vector<pair<long long, long long>> t;

    segtree() {}

    segtree(vector<pair<long long, long long>>& in)
    {
        n = in.size();
        t.resize(n * 4);
        build(0, 0, n - 1, in);
    }

    void build(long long v, long long tl, long long tr, vector<pair<long long, long long>>& in)
    {
        if (tl == tr)
        {
            t[v] = in[tl];
            return;
        }

        long long tm = (tl + tr) / 2;
        build(v * 2 + 1, tl, tm, in);
        build(v * 2 + 2, tm + 1, tr, in);
        t[v].first = min(t[v * 2 + 1].first, t[v * 2 + 2].first);
        t[v].second = max(t[v * 2 + 1].second, t[v * 2 + 2].second);
    }

    pair<long long, long long> get_seg(long long v, long long tl, long long tr, long long l, long long r)
    {
        if (tr < l || r < tl)
        {
            return { INF, -INF };
        }
        if (l <= tl && tr <= r)
        {
            return t[v];
        }

        long long tm = (tl + tr) / 2;
        auto [l1, r1] = get_seg(v * 2 + 1, tl, tm, l, r);
        auto [l2, r2] = get_seg(v * 2 + 2, tm + 1, tr, l, r);
        return { min(l1, l2), max(r1, r2) };
    }

    pair<long long, long long> get(long long l, long long r)
    {
        return get_seg(0, 0, n - 1, l, r);
    }
};

void solve()
{
    long long n, k, m;
    vector<long long> tol, tor;
    cin >> n >> k >> m;
    tol.resize(n, INF);
    tor.resize(n, -INF);
    for (long long i = 0; i < m; i++)
    {
        long long a, b;
        cin >> a >> b;
        a--; b--;
        if (a < b)
        {
            tor[a] = max(tor[a], b);
        }
        else
        {
            tol[a] = min(tol[a], b);
        }
    }

    quemax qmx;
    quemin qmn;
    for (long long i = 0; i < k; i++)
    {
        qmn.push_back(tol[i]);
    }
    vector<pair<long long, long long>> sg(n);
    for (long long i = 0; i < n; i++)
    {
        qmx.push_back(tor[i]);
        if (i - k >= 0)
        {
            qmx.pop_front();
        }
        if (i > 0)
        {
            qmn.pop_front();
            if (i + k - 1 < n)
            {
                qmn.push_back(tol[i + k - 1]);
            }
        }

        sg[i].first = min(qmn.get_min(), i);
        sg[i].second = max(qmx.get_max(), i);
    }

    vector<segtree> sgtbin(LOG);
    sgtbin[0] = segtree(sg);
    for (long long i = 1; i < LOG; i++)
    {
        for (long long j = 0; j < n; j++)
        {
            sg[j] = sgtbin[i - 1].get(sg[j].first, sg[j].second);
        }
        sgtbin[i] = segtree(sg);
    }

    long long q;
    cin >> q;
    while (q--)
    {
        long long a, b;
        cin >> a >> b;
        a--; b--;
        if (a == b)
        {
            cout << 0 << "\n";
            continue;
        }

        auto [finl, finr] = sgtbin.back().get(a, a);
        if (b < finl || finr < b)
        {
            cout << -1 << "\n";
            continue;
        }

        long long left = a, right = a;
        long long ans = 1;
        for (long long i = LOG - 1; i > -1; i--)
        {
            auto [cl, cr] = sgtbin[i].get(left, right);
            if (cl <= b && b <= cr)
            {
                continue;
            }

            ans += (1ll << i);
            left = cl; right = cr;
        }
        cout << ans << "\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    srand(time(NULL));

    int tst = 1;
    //cin >> tst;
    while (tst--)
    {
        solve();
    }

    return 0;
}

/*
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀
⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀
⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀
⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀
⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇
⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁
⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀
⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀
⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀
⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀
⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀
⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀
⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀
⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀
⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀
⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧
⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘
⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀
⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀
<3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3
*/

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