Submission #746081

#	Time	Username	Problem	Language	Result	Execution time	Memory
746081		nguyentunglam	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	837 ms	67212 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
int l[20][N], r[20][N];
int n, m, k;
vector<pair<int, int> > edge[N];

struct IT {
    int f[N << 2], g[N << 2];

    void build(int s, int l, int r) {
        if (l == r) {
            f[s] = g[s] = l;
            return;
        }
        int mid = l + r >> 1;
        build(s << 1, l, mid);
        build(s << 1 | 1, mid + 1, r);
        f[s] = min(f[s << 1], f[s << 1 | 1]);
        g[s] = max(g[s << 1], g[s << 1 | 1]);
    }

    void up(int s, int l, int r, int pos, int val1, int val2) {
        if (l == r) {
            f[s] = val1; g[s] = val2;
            return;
        }
        int mid = l + r >> 1;
        if (pos <= mid) up(s << 1, l, mid, pos, val1, val2);
        else up(s << 1 | 1, mid + 1, r, pos, val1, val2);
        f[s] = min(f[s << 1], f[s << 1 | 1]);
        g[s] = max(g[s << 1], g[s << 1 | 1]);
    }

    pair<int, int> get(int s, int l, int r, int from, int to) {
        if (l > to || r < from) return {1e9, 0};
        if (from <= l && r <= to) return make_pair(f[s], g[s]);
        int mid = l + r >> 1;
        int a, b, c, d;
        tie(a, b) = get(s << 1, l, mid, from, to);
        tie(c, d) = get(s << 1 | 1, mid + 1, r, from, to);
        return make_pair(min(a, c), max(b, d));
    }
} it[20];

int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    cin >> n >> k >> m;
    set<int> s1, s2;
    for(int i = 1; i <= n; i++) l[0][i] = r[0][i] = i, s1.insert(i), s2.insert(i);
    s1.insert(n + 1);
    s2.insert(n + 1);
    for(int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        int from, to;
        if (a < b) {
            from = a; to = min(a + k - 1, b - 1);
        }
        else {
            from = max(a - k + 1, b + 1); to = a;
        }
        edge[b].emplace_back(from, to);
    }

    for(int val = 1; val <= n; val++) {
        for(auto &[from, to] : edge[val]) {
            while (!s1.empty()) {
                auto pos = *s1.lower_bound(from);
                if (pos > to) break;
                l[0][pos] = min(l[0][pos], val);
                s1.erase(pos);
            }
        }
    }

    for(int val = n; val >= 1; val--) {
        for(auto &[from, to] : edge[val]) {
            while (!s2.empty()) {
                auto pos = *s2.lower_bound(from);
                if (pos > to) break;
                r[0][pos] = max(r[0][pos], val);
//                if (pos == 1) cout << from << " " << to << " " << val << endl;
                s2.erase(pos);
            }
        }
    }

    int lg = log2(n);
    for(int j = 0; j <= lg; j++) it[j].build(1, 1, n);
    for(int i = 1; i <= n; i++) it[0].up(1, 1, n, i, l[0][i], r[0][i]);


    for(int j = 1; j <= lg; j++) for(int i = 1; i <= n; i++) {
        tie(l[j][i], r[j][i]) = it[j - 1].get(1, 1, n, l[j - 1][i], r[j - 1][i]);
        it[j].up(1, 1, n, i, l[j][i], r[j][i]);
    }
    int q; cin >> q;
    while (q--) {
        int s, t; cin >> s >> t;
        int left = s, right = s, ans = 0;
        for(int j = lg; j >= 0; j--) {
            int ll, rr;
            tie(ll, rr) = it[j].get(1, 1, n, left, right);
            if (t > rr || t < ll) {
                left = ll; right = rr;
                ans += (1 << j);
            }
        }
        if (ans == (1 << lg << 1) - 1) ans = -2;
        cout << ans + 1 << endl;
    }
}

Compilation message (stderr)

Main.cpp: In member function 'void IT::build(int, int, int)':
Main.cpp:20:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void IT::up(int, int, int, int, int, int)':
Main.cpp:32:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'std::pair<int, int> IT::get(int, int, int, int, int)':
Main.cpp:42:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:54:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:55:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:58:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:59:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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