Submission #1189553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189553		patgra	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	642 ms	56088 KiB

Main

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

int n, k, m, q;
int tBase, maxLog;
vector<int> tf, tb;
vector<vector<int>> tf2, tb2;

void tfMaxEq(int l, int r, int x) {
    l += tBase, r += tBase;
    tf[l] = max(tf[l], x);
    tf[r] = max(tf[r], x);
    while(l / 2 != r / 2) {
        if(l % 2 == 0) tf[l + 1] = max(tf[l + 1], x);
        if(r % 2 == 1) tf[r - 1] = max(tf[r - 1], x);
        l /= 2; r /= 2;
    }
}

void tbMinEq(int l, int r, int x) {
    l += tBase, r += tBase;
    tb[l] = min(tb[l], x);
    tb[r] = min(tb[r], x);
    while(l / 2 != r / 2) {
        if(l % 2 == 0) tb[l + 1] = min(tb[l + 1], x);
        if(r % 2 == 1) tb[r - 1] = min(tb[r - 1], x);
        l /= 2; r /= 2;
    }
}

int tfMax(int i) {
    i += tBase;
    int ans = tf[i];
    while(i) ans = max(ans, tf[i]), i /= 2;
    return ans;
}

int tbMin(int i) {
    i += tBase;
    int ans = tb[i];
    while(i) ans = min(ans, tb[i]), i /= 2;
    return ans;
}

void tf2Set(int i, int j, int x) {
    i += tBase;
    tf2[i][j] = x; i /= 2;
    while(i) tf2[i][j] = max(tf2[2 * i][j], tf2[2 * i + 1][j]), i /= 2;
}

int tf2Max(int l, int r, int j) {
    l += tBase; r += tBase;
    auto ret = max(tf2[l][j], tf2[r][j]);
    while(l / 2 != r / 2) {
        if(l % 2 == 0) ret = max(ret, tf2[l + 1][j]);
        if(r % 2 == 1) ret = max(ret, tf2[r - 1][j]);
        l /= 2; r /= 2;
    }
    return ret;
}

void tb2Set(int i, int j, int x) {
    i += tBase;
    tb2[i][j] = x; i /= 2;
    while(i) tb2[i][j] = min(tb2[2 * i][j], tb2[2 * i + 1][j]), i /= 2;
}

int tb2Min(int l, int r, int j) {
    l += tBase; r += tBase;
    auto ret = min(tb2[l][j], tb2[r][j]);
    while(l / 2 != r / 2) {
        if(l % 2 == 0) ret = min(ret, tb2[l + 1][j]);
        if(r % 2 == 1) ret = min(ret, tb2[r - 1][j]);
        l /= 2; r /= 2;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n >> k >> m;
    k--;
    tBase = 1 << (32 - __builtin_clz(n + 1));
    tf.resize(2 * tBase, 0); 
    tb.resize(2 * tBase, n);
    rep(i, 0, tBase) tf[i + tBase] = tb[i + tBase] = i;
    rep(i, 0, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if(a < b) {
            tfMaxEq(a, min(a + k, b), b);
        }
        else {
            tbMinEq(max(b, a - k), a, b);
        }
    }

    maxLog = 33 - __builtin_clz(n);
    tf2.resize(2 * tBase, vector<int>(maxLog, 0));
    tb2.resize(2 * tBase, vector<int>(maxLog, n));
    rep(i, 0, n) tf2Set(i, 0, tfMax(i));
    rep(i, 0, n) tb2Set(i, 0, tbMin(i));
    rep(j, 1, maxLog) rep(i, 0, n) {
        tf2Set(i, j, tf2Max(tb2Min(i, i, j - 1), tf2Max(i, i, j - 1), j - 1));
        tb2Set(i, j, tb2Min(tb2Min(i, i, j - 1), tf2Max(i, i, j - 1), j - 1));
    }
    
    DEBUG {
        DC << "jpf" << eol;
        rep(j, 0, maxLog) {
            DC << ' ' << (1 << j) << ": ";
            rep(i, 0, n) DC << tf2Max(i, i, j) << ' ';
            DC << eol;
        }
        DC << "jpb" << eol;
        rep(j, 0, maxLog) {
            DC << ' ' << (1 << j) << ": ";
            rep(i, 0, n) DC << tb2Min(i, i, j) << ' ';
            DC << eol;
        }
    }

    cin >> q;
    rep(_, 0, q) {
        int s, t, ans = 1;
        cin >> s >> t;
        s--; t--;
        int s1 = s, s2 = s;
        repD(j, maxLog - 1, -1) {
            int n1 = tb2Min(s1, s2, j);
            int n2 = tf2Max(s1, s2, j);
            if(n1 <= t && t <= n2) continue;
            s1 = n1;
            s2 = n2;
            ans += 1 << j;
        }
        int n1 = tb2Min(s1, s2, 0);
        int n2 = tf2Max(s1, s2, 0);
        if(n1 <= t && t <= n2) cout << ans << '\n';
        else cout << -1 << '\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