Submission #939768

#	Time	Username	Problem	Language	Result	Execution time	Memory
939768		weakweakweak	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	534 ms	331024 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int N = 110000;
int n, k, m, l[N][20], r[N][20], mxst[20][N][20], mnst[20][N][20];
vector <int> laddv[N], lerrv[N], raddv[N], rerrv[N]; //用在走第一步

int getmx (int id, int l, int r) {
    if (l > r) swap(l, r);
    int g = __lg(r - l + 1);
    return max(mxst[id][l][g], mxst[id][r - (1 << g) + 1][g]);
}
int getmn (int id, int l, int r) {
    if (l > r) swap(l, r);
    int g = __lg(r - l + 1);
    return min(mnst[id][l][g], mnst[id][r - (1 << g) + 1][g]);
}


int main () {
    //輸入與走第一步(我用multiset維護)
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> k >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        if (a < b) {
            int c = min(a + k - 1, b - 1);
            raddv[a] . push_back(b);
            rerrv[c] . push_back(b);
        }
        if (a > b) {
            int c = max(a - k + 1, b + 1);
            laddv[a] . push_back(b);
            lerrv[c] . push_back(b);
        }
    }
    //向右走
    multiset <int> mst;
    for (int i = 1; i <= n; i++) {
        for (int x : raddv[i]) mst.insert(x);
        r[i][0] = i;
        if (mst.size()) r[i][0] = max(r[i][0], *mst.rbegin());
        for (int x : rerrv[i]) mst.erase(mst.find(x));
    }
    //向左走
    mst.clear();
    for (int i = n; i >= 1; i--) {
        for (int x : laddv[i]) mst.insert(x);
        l[i][0] = i;
        if (mst.size()) l[i][0] = min(l[i][0], *mst.begin());
        for (int x : lerrv[i]) mst.erase(mst.find(x));
    }


    //倍增好玩
    for (int step = 1; step < 19; step++) {
        //做好st表
        for (int i = 1; i <= n; i++) mxst[step - 1][i][0] = r[i][step - 1],  mnst[step - 1][i][0] = l[i][step - 1];
        for (int j = 1; j < 19; j++) for (int i = 1; i + (1 << j) - 1 <= n; i++) {
            mxst[step - 1][i][j] = max(mxst[step - 1][i][j - 1],    mxst[step - 1][i + (1 << j - 1)][j - 1]);
            mnst[step - 1][i][j] = min(mnst[step - 1][i][j - 1],    mnst[step - 1][i + (1 << j - 1)][j - 1]);
        }
        //倍增倍增
        for (int i = 1; i <= n; i++) {
            r[i][step] = getmx(step - 1, l[i][step - 1], r[i][step - 1]);
            l[i][step] = getmn(step - 1, l[i][step - 1], r[i][step - 1]); 
        }
    }

    //算答案
    int q;
    cin >> q;
    while (q--) {
        int st, ed;
        cin >> st >> ed;
        int res = 0, ll = st, rr = st;
        bool y = 0;
        for (int i = 17; i >= 0; i--) {
            int nll = getmn(i, ll, rr), nrr = getmx(i, ll, rr);
            if (nll <= ed and ed <= nrr) y = 1;
            else {
                ll = nll, rr = nrr;
                res += (1 << i);
            }
        }
        if (!y) cout << -1 << '\n';
        else cout << res + 1 << '\n';
    }
return 0;}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:65:96: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   65 |             mxst[step - 1][i][j] = max(mxst[step - 1][i][j - 1],    mxst[step - 1][i + (1 << j - 1)][j - 1]);
      |                                                                                              ~~^~~
Main.cpp:66:96: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   66 |             mnst[step - 1][i][j] = min(mnst[step - 1][i][j - 1],    mnst[step - 1][i + (1 << j - 1)][j - 1]);
      |                                                                                              ~~^~~

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