oj.uz

Submission #890684

# Submission time Handle Problem Language Result Execution time Memory
890684 2023-12-21T18:27:21 Z EJIC_B_KEDAX Railway Trip 2 (JOI22_ho_t4) C++17
16 / 100
 2000 ms 119528 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';
    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 28 ms 49756 KB Output is correct
2 Correct 27 ms 49756 KB Output is correct
3 Correct 25 ms 49752 KB Output is correct
4 Correct 28 ms 49756 KB Output is correct
5 Correct 34 ms 49864 KB Output is correct
6 Correct 26 ms 49752 KB Output is correct
7 Correct 26 ms 49800 KB Output is correct
8 Correct 25 ms 49756 KB Output is correct
9 Correct 27 ms 49756 KB Output is correct
10 Correct 22 ms 49760 KB Output is correct
11 Correct 27 ms 49756 KB Output is correct
12 Correct 28 ms 49752 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 49756 KB Output is correct
2 Correct 27 ms 49756 KB Output is correct
3 Correct 25 ms 49752 KB Output is correct
4 Correct 28 ms 49756 KB Output is correct
5 Correct 34 ms 49864 KB Output is correct
6 Correct 26 ms 49752 KB Output is correct
7 Correct 26 ms 49800 KB Output is correct
8 Correct 25 ms 49756 KB Output is correct
9 Correct 27 ms 49756 KB Output is correct
10 Correct 22 ms 49760 KB Output is correct
11 Correct 27 ms 49756 KB Output is correct
12 Correct 28 ms 49752 KB Output is correct
13 Correct 73 ms 49756 KB Output is correct
14 Correct 75 ms 50008 KB Output is correct
15 Correct 59 ms 49756 KB Output is correct
16 Correct 86 ms 49752 KB Output is correct
17 Correct 75 ms 50012 KB Output is correct
18 Correct 67 ms 50008 KB Output is correct
19 Correct 83 ms 50012 KB Output is correct
20 Correct 67 ms 49752 KB Output is correct
21 Correct 56 ms 50008 KB Output is correct
22 Correct 74 ms 50012 KB Output is correct
23 Correct 71 ms 49796 KB Output is correct
24 Correct 77 ms 49972 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2029 ms 57260 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2012 ms 119528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2011 ms 61252 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 49756 KB Output is correct
2 Correct 27 ms 49756 KB Output is correct
3 Correct 25 ms 49752 KB Output is correct
4 Correct 28 ms 49756 KB Output is correct
5 Correct 34 ms 49864 KB Output is correct
6 Correct 26 ms 49752 KB Output is correct
7 Correct 26 ms 49800 KB Output is correct
8 Correct 25 ms 49756 KB Output is correct
9 Correct 27 ms 49756 KB Output is correct
10 Correct 22 ms 49760 KB Output is correct
11 Correct 27 ms 49756 KB Output is correct
12 Correct 28 ms 49752 KB Output is correct
13 Correct 73 ms 49756 KB Output is correct
14 Correct 75 ms 50008 KB Output is correct
15 Correct 59 ms 49756 KB Output is correct
16 Correct 86 ms 49752 KB Output is correct
17 Correct 75 ms 50012 KB Output is correct
18 Correct 67 ms 50008 KB Output is correct
19 Correct 83 ms 50012 KB Output is correct
20 Correct 67 ms 49752 KB Output is correct
21 Correct 56 ms 50008 KB Output is correct
22 Correct 74 ms 50012 KB Output is correct
23 Correct 71 ms 49796 KB Output is correct
24 Correct 77 ms 49972 KB Output is correct
25 Execution timed out 2029 ms 57260 KB Time limit exceeded
26 Halted 0 ms 0 KB -