oj.uz

Submission #890686

# Submission time Handle Problem Language Result Execution time Memory
890686 2023-12-21T18:27:53 Z EJIC_B_KEDAX Railway Trip 2 (JOI22_ho_t4) C++17
16 / 100
 224 ms 125648 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 = 100100, Q = 50500, M = 200200, LG = 18;
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].get(i, i), str[l - 1].get(i, i)));
            str[l].update_element(i, str[l - 1].get(stl[l - 1].get(i, i), str[l - 1].get(i, 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 49752 KB Output is correct
2 Correct 29 ms 49668 KB Output is correct
3 Correct 28 ms 49752 KB Output is correct
4 Correct 31 ms 49744 KB Output is correct
5 Correct 29 ms 49756 KB Output is correct
6 Correct 28 ms 49848 KB Output is correct
7 Correct 27 ms 49756 KB Output is correct
8 Correct 32 ms 49752 KB Output is correct
9 Correct 28 ms 49756 KB Output is correct
10 Correct 23 ms 49748 KB Output is correct
11 Correct 30 ms 49732 KB Output is correct
12 Correct 33 ms 49756 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 49752 KB Output is correct
2 Correct 29 ms 49668 KB Output is correct
3 Correct 28 ms 49752 KB Output is correct
4 Correct 31 ms 49744 KB Output is correct
5 Correct 29 ms 49756 KB Output is correct
6 Correct 28 ms 49848 KB Output is correct
7 Correct 27 ms 49756 KB Output is correct
8 Correct 32 ms 49752 KB Output is correct
9 Correct 28 ms 49756 KB Output is correct
10 Correct 23 ms 49748 KB Output is correct
11 Correct 30 ms 49732 KB Output is correct
12 Correct 33 ms 49756 KB Output is correct
13 Correct 79 ms 50012 KB Output is correct
14 Correct 78 ms 50012 KB Output is correct
15 Correct 60 ms 49836 KB Output is correct
16 Correct 77 ms 50012 KB Output is correct
17 Correct 80 ms 50040 KB Output is correct
18 Correct 74 ms 50040 KB Output is correct
19 Correct 84 ms 50020 KB Output is correct
20 Correct 69 ms 50016 KB Output is correct
21 Correct 58 ms 50004 KB Output is correct
22 Correct 81 ms 49940 KB Output is correct
23 Correct 72 ms 49964 KB Output is correct
24 Correct 86 ms 49968 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 116 ms 117148 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 121 ms 120168 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 224 ms 125648 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 49752 KB Output is correct
2 Correct 29 ms 49668 KB Output is correct
3 Correct 28 ms 49752 KB Output is correct
4 Correct 31 ms 49744 KB Output is correct
5 Correct 29 ms 49756 KB Output is correct
6 Correct 28 ms 49848 KB Output is correct
7 Correct 27 ms 49756 KB Output is correct
8 Correct 32 ms 49752 KB Output is correct
9 Correct 28 ms 49756 KB Output is correct
10 Correct 23 ms 49748 KB Output is correct
11 Correct 30 ms 49732 KB Output is correct
12 Correct 33 ms 49756 KB Output is correct
13 Correct 79 ms 50012 KB Output is correct
14 Correct 78 ms 50012 KB Output is correct
15 Correct 60 ms 49836 KB Output is correct
16 Correct 77 ms 50012 KB Output is correct
17 Correct 80 ms 50040 KB Output is correct
18 Correct 74 ms 50040 KB Output is correct
19 Correct 84 ms 50020 KB Output is correct
20 Correct 69 ms 50016 KB Output is correct
21 Correct 58 ms 50004 KB Output is correct
22 Correct 81 ms 49940 KB Output is correct
23 Correct 72 ms 49964 KB Output is correct
24 Correct 86 ms 49968 KB Output is correct
25 Runtime error 116 ms 117148 KB Execution killed with signal 6
26 Halted 0 ms 0 KB -