Submission #971945

#	Time	Username	Problem	Language	Result	Execution time	Memory
971945		maomao90	Railway Trip 2 (JOI22_ho_t4)	C++17	60 / 100	99 ms	76956 KiB

Main

    // Hallelujah, praise the one who set me free
    // Hallelujah, death has lost its grip on me
    // You have broken every chain, There's salvation in your name
    // Jesus Christ, my living hope
    #include <bits/stdc++.h> 
    using namespace std;
     
    #define REP(i, s, e) for (int i = (s); i < (e); i++)
    #define RREP(i, s, e) for (int i = (s); i >= (e); i--)
    template <class T>
    inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
    template <class T>
    inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
    typedef long long ll;
    typedef long double ld;
    #define FI first
    #define SE second
    typedef pair<int, int> ii;
    typedef pair<ll, ll> pll;
    typedef tuple<int, int, int> iii;
    #define ALL(_a) _a.begin(), _a.end()
    #define SZ(_a) (int) _a.size()
    #define pb push_back
    typedef vector<int> vi;
    typedef vector<ll> vll;
    typedef vector<ii> vii;
    typedef vector<iii> viii;
     
    #ifndef DEBUG
    #define cerr if (0) cerr
    #endif
     
    const int INF = 1000000005;
    const ll LINF = 1000000000000000005ll;
    const int MAXN = 200005;
    const int MAXM = 200005;
    const int MAXQ = 200005;
    const int MAXL = 20;
     
    int n, k, m;
    ii ab[MAXM];
    int q;
    ii st[MAXQ];
     
    namespace st4 {
        int p[MAXL][MAXN];
        int mx[MAXN];
        int ans[MAXQ];
     
        int par[MAXN], rnk[MAXN], rt[MAXN];
        void init() {
            REP (i, 1, n + 2) {
                par[i] = i;
                rnk[i] = 1;
                rt[i] = i;
            }
        }
        int findp(int i) {
            if (par[i] == i) {
                return i;
            }
            return par[i] = findp(par[i]);
        }
        bool join(int a, int b) {
            int pa = findp(a), pb = findp(b);
            if (pa == pb) {
                return 0;
            }
            if (rnk[pa] < rnk[pb]) {
                swap(pa, pb);
            }
            if (rnk[pa] == rnk[pb]) {
                rnk[pa]++;
            }
            par[pb] = pa;
            mxto(rt[pa], rt[pb]);
            return 1;
        }
     
        void solve() {
            sort(ab, ab + m, [&] (ii l, ii r) {
                    return l.FI < r.FI;
                    });
            REP (i, 1, n + 1) {
                p[0][i] = -1;
            }
            int prv = 0;
            REP (i, 0, m) {
                auto [a, b] = ab[i];
                if (a > b) {
                    continue;
                }
                REP (j, max(prv, a), b + 1) {
                    cerr << j << ": " << a << '\n';
                    p[0][j] = a;
                }
                mxto(prv, b + 1);
            }
            REP (k, 1, MAXL) {
                REP (i, 1, n + 1) {
                    if (p[k - 1][i] == -1) {
                        p[k][i] = -1;
                    } else {
                        p[k][i] = p[k - 1][p[k - 1][i]];
                    }
                }
            }
            sort(ab, ab + m, [&] (ii l, ii r) {
                    return l.SE > r.SE;
                    });
            init();
            REP (i, 1, n + 1) {
                mx[i] = i;
            }
            REP (i, 0, m) {
                auto [a, b] = ab[i];
                if (a > b) {
                    continue;
                }
                while (rt[findp(a)] < min(a + k, b)) {
                    assert(mxto(mx[rt[findp(a)]], b));
                    join(rt[findp(a)], rt[findp(a)] + 1);
                }
            }
            REP (i, 0, q) {
                auto [s, t] = st[i];
                if (s > t) {
                    continue;
                }
                int res = 0;
                RREP (k, MAXL - 1, 0) {
                    if (p[k][t] != -1 && p[k][t] > s) {
                        t = p[k][t];
                        res += 1 << k;
                    }
                }
                if (mx[s] >= t) {
                    ans[i] = res + 1;
                } else {
                    ans[i] = -1;
                }
            }
        }
        int main() {
            solve();
            REP (i, 0, m) {
                ab[i].FI = n - ab[i].FI + 1;
                ab[i].SE = n - ab[i].SE + 1;
            }
            REP (i, 0, q) {
                st[i].FI = n - st[i].FI + 1;
                st[i].SE = n - st[i].SE + 1;
            }
            solve();
            REP (i, 0, q) {
                cout << ans[i] << '\n';
            }
            return 0;
        }
    }
    namespace st5 {
        int p[MAXL][MAXM];
        int ans[MAXQ];
     
        ii sp[MAXL][MAXN];
        ii qmx(int s, int e) {
            int k = 31 - __builtin_clz(e - s + 1);
            return max(sp[k][s], sp[k][e - (1 << k) + 1]);
        }
     
        int par[MAXN], rnk[MAXN], rt[MAXN];
        void init() {
            REP (i, 1, n + 2) {
                par[i] = i;
                rnk[i] = 1;
                rt[i] = i;
            }
        }
        int findp(int i) {
            if (par[i] == i) {
                return i;
            }
            return par[i] = findp(par[i]);
        }
        bool join(int a, int b) {
            int pa = findp(a), pb = findp(b);
            if (pa == pb) {
                return 0;
            }
            if (rnk[pa] < rnk[pb]) {
                swap(pa, pb);
            }
            if (rnk[pa] == rnk[pb]) {
                rnk[pa]++;
            }
            par[pb] = pa;
            mxto(rt[pa], rt[pb]);
            return 1;
        }
     
        int main() {
            sort(ab, ab + m, [&] (ii l, ii r) {
                    return l.SE > r.SE;
                    });
            init();
            REP (i, 1, n + 1) {
                sp[0][i] = {i, -1};
            }
            REP (i, 0, m) {
                auto [a, b] = ab[i];
                if (a > b) {
                    continue;
                }
                while (rt[findp(a)] < min(a + k, b)) {
                    assert(mxto(sp[0][rt[findp(a)]], {b, i}));
                    join(rt[findp(a)], rt[findp(a)] + 1);
                }
            }
            REP (i, 1, n + 1) {
                cerr << i << ": " << sp[0][i].FI << ' ' << sp[0][i].SE << '\n';
            }
            REP (k, 1, MAXL) {
                REP (i, 1, n + 1 - (1 << k - 1)) {
                    sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + (1 << k - 1)]);
                }
            }
            REP (i, 0, m) {
                auto [a, b] = ab[i];
                p[0][i] = qmx(a, b).SE;
            }
            REP (k, 1, MAXL) {
                REP (i, 0, m + 1) {
                    if (p[k - 1][i] == -1) {
                        p[k][i] = -1;
                    } else {
                        p[k][i] = p[k - 1][p[k - 1][i]];
                    }
                }
            }
            REP (i, 0, q) {
                auto [s, t] = st[i];
                if (s > t) {
                    continue;
                }
                int u = sp[0][s].SE;
                cerr << ' ' << u << '\n';
                if (u == -1) {
                    ans[i] = -1;
                    continue;
                }
                if (ab[u].SE >= t) {
                    ans[i] = 1;
                    continue;
                }
                int nu = qmx(min(s + k, ab[u].SE), ab[u].SE).SE;
                cerr << "  " << nu << '\n';
                if (nu == -1 || nu == u) {
                    ans[i] = -1;
                    continue;
                }
                u = nu;
                ans[i] = 2;
                if (ab[u].SE >= t) {
                    continue;
                }
                RREP (k, MAXL - 1, 0) {
                    if (p[k][u] != -1 && ab[p[k][u]].SE < t) {
                        u = p[k][u];
                        ans[i] += 1 << k;
                    }
                }
                cerr << "   " << u << '\n';
                if (p[0][u] == -1 || ab[p[0][u]].SE < t) {
                    ans[i] = -1;
                } else {
                    ans[i]++;
                }
            }
            REP (i, 0, q) {
                cout << ans[i] << '\n';
            }
            return 0;
        }
    }
     
    int main() {
    #ifndef DEBUG
        ios::sync_with_stdio(0), cin.tie(0);
    #endif
        cin >> n >> k >> m;
        REP (i, 0, m) {
            cin >> ab[i].FI >> ab[i].SE;
        }
        cin >> q;
        REP (i, 0, q) {
            cin >> st[i].FI >> st[i].SE;
        }
        if (k == n - 1) {
            st4::main();
        } else {
            st5::main();
        }
        return 0;
    }

Compilation message (stderr)

Main.cpp: In function 'int st5::main()':
Main.cpp:223:44: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  223 |                 REP (i, 1, n + 1 - (1 << k - 1)) {
      |                                          ~~^~~
Main.cpp:8:49: note: in definition of macro 'REP'
    8 |     #define REP(i, s, e) for (int i = (s); i < (e); i++)
      |                                                 ^
Main.cpp:224:72: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  224 |                     sp[k][i] = max(sp[k - 1][i], sp[k - 1][i + (1 << k - 1)]);
      |                                                                      ~~^~~

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