Submission #885192

#	Time	Username	Problem	Language	Result	Execution time	Memory
885192		makrav	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	185 ms	48304 KiB

Main

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vei;
typedef vector<vei> vevei;

#define all(a) (a).begin(), (a).end()
#define sz(a) (int) a.size()
#define con cout << "NO\n"
#define coe cout << "YES\n";
#define str string
#define pb push_back
#define ff first
#define sc second
#define ss second
#define pii pair<int, int>
#define mxe max_element
#define mne min_element
#define stf shrink_to_fit
#define f(i, l, r) for (int i = (l); i < (r); i++)
#define double ld

struct segtree {
    int n, tim;
    vector<pair<int, int>> t;

    segtree() = default;
    segtree(int n_) {
        n = n_;
        tim = 0;
        t.resize(4 * n, { 0, -1 });
    }

    void upd(int v, int tl, int tr, int l, int r, int x) {
        if (l <= tl && tr <= r) {
            t[v] = { x, tim };
            return;
        }
        if (tr <= l || tl >= r) return;
        int tm = (tl + tr) / 2;
        upd(v * 2, tl, tm, l, r, x);
        upd(v * 2 + 1, tm, tr, l, r, x);
    }

    pair<int, int> get(int v, int tl, int tr, int x) {
        if (tl + 1 == tr) {
            return t[v];
        }
        int tm = (tl + tr) / 2;
        pair<int, int> res;
        if (x < tm) {
            res = get(v * 2, tl, tm, x);
        }
        else {
            res = get(v * 2 + 1, tm, tr, x);
        }
        if (res.sc > t[v].sc) return res;
        else return t[v];
    }
};

const int MAXN = 100010;

vector<int> Log_2(MAXN, 0);
void fill() {
    for (int i = 2; i < MAXN; i++) {
        Log_2[i] = Log_2[i / 2] + 1;
    }
}

struct SparseTableMax {
    int n;
    vector<int> a;
    vector<vector<int>> mx;

    SparseTableMax(int n_, vector<int> a_) {
        n = n_;
        a = a_;
        mx.resize(Log_2[n] + 1, vector<int>(n, -1));
        build();
    }

    int comp(int i, int j) {
        return (a[i] > a[j] ? i : j);
    }

    void build() {
        for (int i = n - 1; i >= 0; i--) {
            mx[0][i] = i;
            int st = 1;
            while ((1 << st) + i <= n) {
                mx[st][i] = comp(mx[st - 1][i], mx[st - 1][(1 << (st - 1)) + i]);
                st++;
            }
        }
    }

    int req(int l, int r) {
        bool sw = false;
        int sz = r - l + 1;
        int otr1 = mx[Log_2[sz]][l];
        int ot2 = mx[Log_2[sz]][r - (1 << Log_2[sz]) + 1];
        return comp(otr1, ot2);
    }
};

struct SparseTableMin {
    int n;
    vector<int> a;
    vector<vector<int>> mx;

    SparseTableMin(int n_, vector<int> a_) {
        n = n_;
        a = a_;
        mx.resize(Log_2[n] + 1, vector<int>(n, -1));
        build();
    }

    int comp(int i, int j) {
        return (a[i] < a[j] ? i : j);
    }

    void build() {
        for (int i = n - 1; i >= 0; i--) {
            mx[0][i] = i;
            int st = 1;
            while ((1 << st) + i <= n) {
                mx[st][i] = comp(mx[st - 1][i], mx[st - 1][(1 << (st - 1)) + i]);
                st++;
            }
        }
    }

    int req(int l, int r) {
        bool sw = false;
        int sz = r - l + 1;
        int otr1 = mx[Log_2[sz]][l];
        int ot2 = mx[Log_2[sz]][r - (1 << Log_2[sz]) + 1];
        return comp(otr1, ot2);
    }
};

int bfs(int n, vector<vector<int>> g, int s, int gl) {
    vector<int> d(n, -1);
    d[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        auto v = q.front();
        q.pop();
        for (auto& u : g[v]) {
            if (d[u] == -1) {
                d[u] = d[v] + 1;
                q.push(u);
            }
        }
    }
    return d[gl];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    fill();
    int n, k; cin >> n >> k;
    int m; cin >> m;
    vector<pair<int, int>> a(m);
    f(i, 0, m) {
        cin >> a[i].ff >> a[i].sc;
        a[i].ff--;
        a[i].sc--;
    }
    int q; cin >> q;
    vector<pair<int, int>> req(q);
    f(i, 0, q) {
        cin >> req[i].ff >> req[i].sc;
        req[i].ff--;
        req[i].sc--;
    }

    vector<pair<int, int>> tor, tol;
    f(i, 0, m) {
        if (a[i].ff < a[i].sc) {
            tor.pb(a[i]);
        }
        else {
            tol.pb(a[i]);
        }
    }

    segtree sg(n);
    f(i, 0, n) {
        sg.upd(1, 0, n, i, i + 1, i);
    }
    sort(all(tor), [](pair<int, int> a, pair<int, int> b) {
        return a.sc < b.sc;
        });
    for (int i = 0; i < sz(tor); i++) {
        sg.tim++;
        sg.upd(1, 0, n, tor[i].ff, min(tor[i].sc + 1, tor[i].ff + k), tor[i].sc);
    }
    sort(all(tol), [](pair<int, int> a, pair<int, int> b) {
        return a.sc < b.sc;
        });
    segtree sg2(n);
    f(i, 0, n) {
        sg2.upd(1, 0, n, i, i + 1, i);
    }
    for (int i = sz(tol) - 1; i >= 0; i--) {
        sg2.tim++;
        sg2.upd(1, 0, n, max(tol[i].ff - k + 1, tol[i].sc), tol[i].ff + 1, tol[i].sc);
    }

    vector<pair<int, int>> seg1(n);
    f(i, 0, n) {
        seg1[i] = { sg2.get(1, 0, n, i).ff, sg.get(1, 0, n, i).ff };
    }

    vector<int> RIGHT(n), LEFT(n);
    f(i, 0, n) {
        RIGHT[i] = seg1[i].sc;
        LEFT[i] = seg1[i].ff;
    }

    SparseTableMax sp(n, RIGHT);
    SparseTableMin sp2(n, LEFT);
    vector<pair<int, int>> g(n);
    for (int i = 0; i < n; i++) {
        int ir = sp.req(seg1[i].ff, seg1[i].sc);
        int il = sp2.req(seg1[i].ff, seg1[i].sc);
        g[i] = { il, ir };
    }

    vector<vector<pair<int, int>>> up(n, vector<pair<int, int>>(19));
    f(i, 0, n) up[i][0] = g[i];

    auto comp_r = [&](int i, int j) {
        return (RIGHT[i] < RIGHT[j] ? j : i);
        };

    auto comp_l = [&](int i, int j) {
        return (LEFT[i] > LEFT[j] ? j : i);
        };

    for (int j = 1; j < 19; j++) {
        for (int i = 0; i < n; i++) {
            auto p = up[i][j - 1];
            auto p2 = up[p.ff][j - 1], p3 = up[p.sc][j - 1];
            int l_ind = comp_l(p2.ff, comp_l(p2.sc, comp_l(p3.ff, p3.sc)));
            int r_ind = comp_r(p2.ff, comp_r(p2.sc, comp_r(p3.ff, p3.sc)));
            up[i][j] = { l_ind, r_ind };
        }
    }

    for (auto& u : req) {
        if (u.ff == u.sc) {
            cout << "0\n";
            continue;
        }
        if (LEFT[u.ff] <= u.sc && u.sc <= RIGHT[u.ff]) {
            cout << "1\n";
            continue;
        }
        auto rs = up[u.ff][18];
        if (u.sc < LEFT[rs.ff] || u.sc > RIGHT[rs.sc]) {
            cout << "-1\n";
            continue;
        }
        int ans = 0;
        int LF = u.ff, RG = u.ff;
        for (int j = 18; j >= 0; j--) {
            auto rs1 = up[LF][j], rs2 = up[RG][j];
            int l_ind = comp_l(rs1.ff, comp_l(rs1.sc, comp_l(rs2.ff, rs2.sc)));
            int r_ind = comp_r(rs1.ff, comp_r(rs1.sc, comp_r(rs2.ff, rs2.sc)));
            if (u.sc < LEFT[l_ind] || u.sc > RIGHT[r_ind]) {
                LF = l_ind;
                RG = r_ind;
                ans += (1 << j);
            }
        }
        assert(ans + 2 <= n);
        cout << ans + 2 << '\n';
    }

    return 0;
}

Compilation message (stderr)

Main.cpp: In member function 'int SparseTableMax::req(int, int)':
Main.cpp:103:14: warning: unused variable 'sw' [-Wunused-variable]
  103 |         bool sw = false;
      |              ^~
Main.cpp: In member function 'int SparseTableMin::req(int, int)':
Main.cpp:139:14: warning: unused variable 'sw' [-Wunused-variable]
  139 |         bool sw = false;
      |              ^~

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