Submission #800579

#	Time	Username	Problem	Language	Result	Execution time	Memory
800579		caganyanmaz	Railway Trip 2 (JOI22_ho_t4)	C++17	11 / 100	759 ms	117252 KiB

Main

#include <bits/stdc++.h>
#define int int64_t
#define mp(x...) array<int, 2>({x})
#define pb push_back
using namespace std;

constexpr static int MXSIZE = 1e5;
constexpr static int INF = 1e8;
constexpr static int MXLOG = 30;

int n, k;
vector<int> rs[MXSIZE], re[MXSIZE], ls[MXSIZE], le[MXSIZE];
array<int, 2> st[MXLOG][MXSIZE<<2];

array<int, 2> merge(array<int, 2> a, array<int, 2> b)
{
        return mp(min(a[0], b[0]), max(a[1], b[1]));
}

void build(int i)
{
        for (int j = n-1; j >= 0; j--) st[i][j] = merge(st[i][j<<1], st[i][(j<<1)|1]);
}

array<int, 2> get(int i, int l, int r)
{
        array<int, 2> res = {INF, -INF};
        for (l+=n,r+=n;r>l;r>>=1,l>>=1)
        {
                if (l&1) res = merge(res, st[i][l++]);
                if (r&1) res = merge(res, st[i][--r]);
        }
        return res;
}

int32_t main()
{
        cin >> n >> k;
        int m;
        cin >> m;
        for (int i = 0; i < m; i++)
        {
                int a, b;
                cin >> a >> b;
                a--, b--;
                if (a < b)
                {
                        rs[a].pb(b);
                        if (a + k < n)
                                re[a+k].pb(b);
                }
                else
                {
                        ls[a].pb(b);
                        if (a - k >= 0)
                                le[a-k].pb(b);
                }
        }
        multiset<int> s;
        for (int i = 0; i < n; i++)
        {
                for (int j : rs[i])
                        s.insert(j);
                for (int j : re[i])
                        s.erase(j);
                if (s.empty())
                        st[0][i+n][1] = i;
                else
                        st[0][i+n][1] = *s.rbegin();
        }
        s.clear();
        for (int i = n-1; i >= 0; i--)
        {
                for (int j : ls[i])
                        s.insert(j);
                for (int j : le[i])
                        s.erase(j);
                if (s.empty())
                        st[0][i+n][0] = i;
                else
                        st[0][i+n][0] = *s.begin();
        }
        build(0);
        for (int i = 1; i < MXLOG; i++)
        {
                for (int j = n; j < n*2; j++)
                        st[i][j] = get(i-1, st[i-1][j][0], st[i-1][j][1]+1);
                build(i);
        }
        int q;
        cin >> q;
        for (int j = 0; j < q; j++)
        {
                int sp, tp;
                cin >> sp >> tp;
                sp--, tp--;
                int dist = 0, l = sp, r = sp;
                for (int i = MXLOG-1; i >= 0; i--)
                {
                        auto [nl, nr] = get(i, l, r+1);
                        if (nl > tp || nr < tp)
                        {
                                l = nl, r = nr;
                                dist = dist|(1<<i);
                        }
                }
                if (dist > INF)
                {
                        cout << "-1\n";
                }
                else
                {
                        auto [nl, nr] = get(0, l, r+1);
                        assert(nl <= tp && tp <= nr);
                        cout << (dist+1) << "\n";
                }
        }
}

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