Submission #1267208

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267208		tvgk	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	718 ms	59460 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
const long mxN = 2e5 + 7, inf = 1e9 + 7;

ii lazy[mxN * 4], tree[mxN * 4][20], rng[mxN * 4][20];
int n, m;

void Gen(int j = 1, int l = 1, int r = n)
{
    lazy[j].fi = inf;
    lazy[j].se = 0;

    if (l == r)
    {
        lazy[j].fi = lazy[j].se = l;
        return;
    }

    int mid = (l + r) / 2;
    Gen(j * 2, l, mid);
    Gen(j * 2 + 1, mid + 1, r);
}

void Upd(int u, int v, int nw, int j = 1, int l = 1, int r = n)
{
    if (r < u || v < l)
        return;

    if (u <= l && r <= v)
    {
        lazy[j].fi = min(lazy[j].fi, nw);
        lazy[j].se = max(lazy[j].se, nw);
        return;
    }

    int mid = (l + r) / 2;
    Upd(u, v, nw, j * 2, l, mid);
    Upd(u, v, nw, j * 2 + 1, mid + 1, r);
}

ii cmp(ii u, ii v)
{
    u.fi = min(u.fi, v.fi);
    u.se = max(u.se, v.se);
    return u;
}

void Down(int j = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        rng[l][0] = lazy[j];
        return;
    }
    lazy[j * 2] = cmp(lazy[j * 2], lazy[j]);
    lazy[j * 2 + 1] = cmp(lazy[j * 2 + 1], lazy[j]);

    int mid = (l + r) / 2;
    Down(j * 2, l, mid);
    Down(j * 2 + 1, mid + 1, r);
}

void Build(int id, int j = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        tree[j][id] = rng[l][id];
        return;
    }

    int mid = (l + r) / 2;
    Build(id, j * 2, l, mid);
    Build(id, j * 2 + 1, mid + 1, r);
    tree[j][id] = cmp(tree[j * 2][id], tree[j * 2 + 1][id]);
}

ii Get(int id, int u, int v, int j = 1, int l = 1, int r = n)
{
    if (r < u || v < l)
        return {inf, 0};

    if (u <= l && r <= v)
        return tree[j][id];

    int mid = (l + r) / 2;
    return cmp(Get(id, u, v, j * 2, l, mid), Get(id, u, v, j * 2 + 1, mid + 1, r));
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    int k;
    cin >> n >> k;
    cin >> m;
    k--;
    Gen();
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;

        if (u < v)
            Upd(u, min(u + k, v), v);
        else
            Upd(max(u - k, v), u, v);
    }
    Down();

    Build(0);
    for (int lg = 1; lg <= 18; lg++)
    {
        for (int i = 1; i <= n; i++)
            rng[i][lg] = Get(lg - 1, rng[i][lg - 1].fi, rng[i][lg - 1].se);
        Build(lg);
    }

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int u, v;
        cin >> u >> v;

        int l = u, r = u, base = 0, ans = inf;
        for (int j = 18; j >= 0; j--)
        {
            ii tmp = Get(j, l, r);
            if (tmp.fi <= v && v <= tmp.se)
                ans = base + (1 << j);
            else
            {
                l = tmp.fi;
                r = tmp.se;
                base += (1 << j);
            }
        }

        if (ans >= inf)
            cout << -1 << '\n';
        else
            cout << ans << '\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