oj.uz

Submission #890689

# Submission time Handle Problem Language Result Execution time Memory
890689 2023-12-21T18:31:19 Z EJIC_B_KEDAX Railway Trip 2 (JOI22_ho_t4) C++17
16 / 100
 1218 ms 125708 KB 
#ifdef LOCAL
    //#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
#include <random>

#ifndef LOCAL
    //#pragma GCC optimize("O3")
    //#pragma GCC optimize("Ofast")
    //#pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using ld = long double;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

template<typename T>
struct segment_tree_default {
    std::vector<T> a{};
    void (*mrg)(T&, const T&, const T&);
    size_t size{};
    T e;
    segment_tree_default(int n, void (*merge)(T&, const T&, const T&), T neutral) {
        mrg = merge;
        e = neutral;
        size = 1;
        while (size < n) {
            size <<= 1;
        }
        a.resize(2 * size - 1, e);
    }
    segment_tree_default() = default;
    void update_element(int ind, const T& value) {
        ind += size - 1;
        a[ind] = value;
        while (ind) {
            ind = (ind - 1) / 2;
            mrg(a[ind], a[2 * ind + 1], a[2 * ind + 2]);
        }
    }
    void update_all(std::vector<T>& values) {
        while (size < values.size()) {
            size <<= 1;
        }
        a.resize(2 * size - 1);
        for (int i = size - 1; i < 2 * size - 1; i++) {
            if (i - size + 1 < values.size()) {
                a[i] = values[i - size + 1];
            } else {
                a[i] = e;
            }
        }
        for (int i = size - 2; i >= 0; i--) {
            mrg(a[i], a[2 * i + 1], a[2 * i + 2]);
        }
    }
    T get(int l, int r, int l1 = 0, int r1 = -1, int i = 0) {
        if (r1 == -1) {
            r1 += size;
        }
        if (l1 >= l && r1 <= r) {
            return a[i];
        }
        if (r1 < l || l1 > r) {
            return e;
        }
        T res;
        mrg(res, get(l, r, l1, (l1 + r1) / 2, 2 * i + 1), get(l, r, (l1 + r1) / 2 + 1, r1, 2 * i + 2));
        return res;
    }
};

void mn(int& to, const int& a, const int& b) {
    to = min(a, b);
}

void mx(int& to, const int& a, const int& b) {
    to = max(a, b);
}

struct segment {
    int v, l, r;
};

bool cmp (const segment& a, const segment& b) {
    if (a.l < b.l) {
        return true;
    }
    if (a.l > b.l) {
        return false;
    }
    return a.r < b.r;
}

bool operator < (const segment& a, const segment& b) {
    if (a.v < b.v) {
        return true;
    }
    if (a.v > b.v) {
        return false;
    }
    if (a.l < b.l) {
        return true;
    }
    if (a.l > b.l) {
        return false;
    }
    return a.r < b.r;
}

mt19937_64 mt(418);

void solve();
void init();

int32_t main() {
#ifndef LOCAL
    cin.tie(nullptr)->sync_with_stdio(false);
#endif
    // srand(time(0));
    init();
    cout << fixed << setprecision(20);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}

const int N = 1 << 17, Q = 50500, M = 200200, LG = 17;
segment_tree_default<int> stl[LG], str[LG];
int a[M], b[M], szl = 0, szr = 0;
vector<int> start_l[N], start_r[N], end_l[N], end_r[N];
segment seg_l[M], seg_r[M];
set<segment> nwl, nwr;

void init() {
    for (int i = 0; i < LG; i++) {
        stl[i] = segment_tree_default<int>(N, mn, INT32_MAX);
        str[i] = segment_tree_default<int>(N, mx, INT32_MIN);
    }
}

void solve() {
    int n, k, m;
    cin >> n >> k >> m;
    for (int i = 0; i < m; i++) {
        cin >> a[i] >> b[i]; a[i]--; b[i]--;
    }
    for (int i = 0; i < m; i++) {
        if (a[i] < b[i]) {
            start_r[a[i]].push_back(szr);
            end_r[min(b[i], a[i] + k - 1)].push_back(szr);
            seg_r[szr++] = {-b[i], a[i], min(b[i], a[i] + k - 1)};
        } else {
            start_l[max(b[i], a[i] - k + 1)].push_back(szl);
            end_l[a[i]].push_back(szl);
            seg_l[szl++] = {b[i], max(b[i], a[i] - k + 1), a[i]};
        }
    }
    nwl.insert({n, 0, 0});
    nwr.insert({1, 0, 0});
    for (int i = 0; i < n; i++) {
        for (int j : start_l[i]) {
            nwl.insert(seg_l[j]);
        }
        // cout << min((*nwl.begin()).v, i) << ' ';
        stl[0].update_element(i, min((*nwl.begin()).v, i));
        for (int j : end_l[i]) {
            nwl.erase(seg_l[j]);
        }
    }
    // cout << '\n';
    for (int i = 0; i < n; i++) {
        for (int j : start_r[i]) {
            nwr.insert(seg_r[j]);
        }
        // cout << max(-(*nwr.begin()).v, i) << ' ';
        str[0].update_element(i, max(-(*nwr.begin()).v, i));
        for (int j : end_r[i]) {
            nwr.erase(seg_r[j]);
        }
    }
    // cout << '\n';
    // assert(n <= 10000);
    for (int l = 1; l < LG; l++) {
        for (int i = 0; i < n; i++) {
            stl[l].update_element(i, stl[l - 1].get(stl[l - 1].a[N - 1 + i], str[l - 1].a[N - 1 + i]));
            str[l].update_element(i, str[l - 1].get(stl[l - 1].a[N - 1 + i], str[l - 1].a[N - 1 + i]));
        }
    }
    assert(n <= 10000);
    int q;
    cin >> q;
    while (q--) {
        int l, r;
        cin >> l >> r; l--; r--;
        int nw = 0, left = l, right = l;
        for (int i = LG - 1; i >= 0; i--) {
            int new_l = stl[i].get(left, right), new_r = str[i].get(left, right);
            if (r > new_r || r < new_l) {
                left = new_l;
                right = new_r;
                nw += 1 << i;
            }
        }
        int new_l = stl[0].get(left, right), new_r = str[0].get(left, right);
        // cout << nw << ' ' << new_l << ' ' << new_r << '\n';
        nw++;
        if (new_l <= r && r <= new_r) {
            cout << nw << '\n';
        } else {
            cout << "-1\n";
        }
    }
}

Compilation message

Main.cpp: In instantiation of 'segment_tree_default<T>::segment_tree_default(int, void (*)(T&, const T&, const T&), T) [with T = int]':
Main.cpp:143:60:   required from here
Main.cpp:31:21: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |         while (size < n) {
      |                ~~~~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 50264 KB Output is correct
2 Correct 24 ms 50268 KB Output is correct
3 Correct 22 ms 50264 KB Output is correct
4 Correct 24 ms 50264 KB Output is correct
5 Correct 25 ms 50264 KB Output is correct
6 Correct 23 ms 50296 KB Output is correct
7 Correct 23 ms 50328 KB Output is correct
8 Correct 22 ms 50520 KB Output is correct
9 Correct 23 ms 50268 KB Output is correct
10 Correct 20 ms 50268 KB Output is correct
11 Correct 28 ms 50520 KB Output is correct
12 Correct 28 ms 50260 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 50264 KB Output is correct
2 Correct 24 ms 50268 KB Output is correct
3 Correct 22 ms 50264 KB Output is correct
4 Correct 24 ms 50264 KB Output is correct
5 Correct 25 ms 50264 KB Output is correct
6 Correct 23 ms 50296 KB Output is correct
7 Correct 23 ms 50328 KB Output is correct
8 Correct 22 ms 50520 KB Output is correct
9 Correct 23 ms 50268 KB Output is correct
10 Correct 20 ms 50268 KB Output is correct
11 Correct 28 ms 50520 KB Output is correct
12 Correct 28 ms 50260 KB Output is correct
13 Correct 50 ms 50672 KB Output is correct
14 Correct 49 ms 50268 KB Output is correct
15 Correct 36 ms 50268 KB Output is correct
16 Correct 48 ms 50268 KB Output is correct
17 Correct 50 ms 50264 KB Output is correct
18 Correct 42 ms 50264 KB Output is correct
19 Correct 48 ms 50264 KB Output is correct
20 Correct 43 ms 50264 KB Output is correct
21 Correct 36 ms 50264 KB Output is correct
22 Correct 49 ms 50268 KB Output is correct
23 Correct 55 ms 50268 KB Output is correct
24 Correct 58 ms 50416 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1109 ms 117616 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 834 ms 120824 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 1218 ms 125708 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 50264 KB Output is correct
2 Correct 24 ms 50268 KB Output is correct
3 Correct 22 ms 50264 KB Output is correct
4 Correct 24 ms 50264 KB Output is correct
5 Correct 25 ms 50264 KB Output is correct
6 Correct 23 ms 50296 KB Output is correct
7 Correct 23 ms 50328 KB Output is correct
8 Correct 22 ms 50520 KB Output is correct
9 Correct 23 ms 50268 KB Output is correct
10 Correct 20 ms 50268 KB Output is correct
11 Correct 28 ms 50520 KB Output is correct
12 Correct 28 ms 50260 KB Output is correct
13 Correct 50 ms 50672 KB Output is correct
14 Correct 49 ms 50268 KB Output is correct
15 Correct 36 ms 50268 KB Output is correct
16 Correct 48 ms 50268 KB Output is correct
17 Correct 50 ms 50264 KB Output is correct
18 Correct 42 ms 50264 KB Output is correct
19 Correct 48 ms 50264 KB Output is correct
20 Correct 43 ms 50264 KB Output is correct
21 Correct 36 ms 50264 KB Output is correct
22 Correct 49 ms 50268 KB Output is correct
23 Correct 55 ms 50268 KB Output is correct
24 Correct 58 ms 50416 KB Output is correct
25 Runtime error 1109 ms 117616 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -