oj.uz

Submission #593817

# Submission time Handle Problem Language Result Execution time Memory
593817 2022-07-11T15:56:49 Z vovik Railway Trip 2 (JOI22_ho_t4) C++17
100 / 100
 934 ms 101120 KB 
#include <bits/stdc++.h>

namespace IO {
    const int DPAIRSIZ = 1 << 10;
    char BB[DPAIRSIZ], *SS = BB, *TT = BB;

    inline char getcha() {
        return SS == TT && (TT = (SS = BB) + fread(BB, 1, DPAIRSIZ, stdin), SS == TT) ? EOF : *SS++;
    }

    template<typename T = int>
    inline T read() {
        T x = 0;
        int fu = 1;
        char c = getcha();
        while (c > 57 || c < 48) {
            if (c == 45) fu = -1;
            c = getcha();
        }
        while (c <= 57 && c >= 48) {
            x = x * 10 + c - 48;
            c = getcha();
        }
        x *= fu;
        return x;
    }

    template<typename T>
    inline void read(T &x) {
        x = 0;
        int fu = 1;
        char c = getcha();
        while (c > 57 || c < 48) {
            if (c == 45) fu = -1;
            c = getcha();
        }
        while (c <= 57 && c >= 48) {
            x = x * 10 + c - 48;
            c = getcha();
        }
        x *= fu;
    }

    template<typename T>
    inline void read(T *bg, T *ed) { while (bg != ed) read(*bg++); }

    inline void read(char &ch) {
        ch = getcha();
        while (ch <= 32) ch = getcha();
    }

    inline void read(char *s) {
        char ch = getcha();
        while (ch <= 32) ch = getcha();
        while (ch > 32) *s++ = ch, ch = getcha();
        *s = '\0';
    }

    inline void read(std::string &s) {
        char ch = getcha();
        while (ch <= 32) ch = getcha();
        while (ch > 32) s.push_back(ch), ch = getcha();
    }

    inline void sread(char *s) {
        char ch = getcha();
        while (ch < 32) ch = getcha();
        while (ch >= 32) *s++ = ch, ch = getcha();
        *s = '\0';
    }

    inline void pread(char *&s) {
        char ch = getcha();
        while (ch <= 32) ch = getcha();
        while (ch > 32) *s++ = ch, ch = getcha();
        *s = '\0';
    }

    inline void spread(char *&s) {
        char ch = getcha();
        while (ch < 32) ch = getcha();
        while (ch >= 32) *s++ = ch, ch = getcha();
        *s = '\0';
    }

    template<typename T, typename ...Args>
    inline void read(T &x, Args &...args) {
        read(x);
        read(args...);
    }

    char out[DPAIRSIZ], *Out = out;
#define flush() fwrite(out, 1, Out - out, stdout)

    inline void putcha(char x) {
        *Out++ = x;
        if (Out - out >= (DPAIRSIZ)) flush(), Out = out;
    }

    template<typename T>
    inline void fprint(T x) {
        if (x < 0) putcha(45), x = -x;
        if (x > 9) fprint(x / 10);
        putcha(x % 10 + 48);
    }

    inline void print() { putcha(10); }

    template<typename T>
    inline void print(T x) {
        fprint(x);
        putcha(10);
    }

    inline void print(char *ch) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(10);
    }

    inline void put(char *ch) { while (*ch != '\0') putcha(*(ch++)); }

    inline void print(const char *ch) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(10);
    }

    inline void put(const char *ch) { while (*ch != '\0') putcha(*(ch++)); }

    template<typename T, typename ...Args>
    inline void print(T x, Args ...args) {
        fprint(x);
        putcha(32);
        print(args...);
    }

    template<typename ...Args>
    inline void print(const char *ch, Args ...args) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(32);
        print(args...);
    }

    template<typename ...Args>
    inline void print(char *ch, Args ...args) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(32);
        print(args...);
    }

    template<typename T, typename ...Args>
    inline void printl(T x, Args ...args) {
        fprint(x);
        putcha(10);
        printl(args...);
    }

    template<typename ...Args>
    inline void printl(const char *ch, Args ...args) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(10);
        printl(args...);
    }

    template<typename ...Args>
    inline void printl(char *ch, Args ...args) {
        while (*ch != '\0') putcha(*(ch++));
        putcha(10);
        printl(args...);
    }

    template<typename T>
    inline void sprint(T x) {
        fprint(x);
        putcha(32);
    }

    template<typename T, typename ...Args>
    inline void sprint(T x, Args ...args) {
        fprint(x);
        putcha(32);
        sprint(args...);
    }

    template<typename T>
    inline void sprint(T *bg, T *ed) { while (bg != ed) sprint(*bg++); }

    template<typename T>
    inline void print(T *bg, T *ed) {
        while (bg != ed) sprint(*bg++);
        putcha(10);
    }

    template<typename T>
    inline void printl(T *bg, T *ed) { while (bg != ed) print(*bg++); }

    class AutoFlush {
    public:
        ~AutoFlush() { flush(); }
    } __AutoFlush;
} // namespace IO
using namespace IO;

#define vc vector

#define nd node*
#define pnd pair<nd, nd>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vc<pll> vpll;
typedef vc<vll> vvll;
typedef vc<vpll> vvpll;

template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};


template<typename T>
inline void sort(T &a) {
    sort(a.begin(), a.end());
}

template<typename T>
inline void unique(T &a) {
    a.resize(unique(a.begin(), a.end()) - a.begin());
}

template<typename T>
inline void reverse(T &a) {
    reverse(a.begin(), a.end());
}

const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;


const ll N = 200005;
pair<int, int> t[17][N * 4];
pair<int, int> up[17][N];

void build(int id, int v = 1, int l = 0, int r = N - 1) {
    if (l == r) return void(t[id][v] = up[id][l]);
    int mid = (l + r) / 2;
    build(id, v * 2, l, mid), build(id, v * 2 + 1, mid + 1, r);
    t[id][v].first = min(t[id][v * 2].first, t[id][v * 2 + 1].first);
    t[id][v].second = max(t[id][v * 2].second, t[id][v * 2 + 1].second);
}

pair<int, int> get(int id, int l_, int r_, int v = 1, int l = 0, int r = N - 1) {
    if (l_ <= l && r <= r_) return t[id][v];
    if (r < l_ || r_ < l) return {1e9, -1e9};
    int mid = (l + r) / 2;
    pair<int, int> ans = get(id, l_, r_, v * 2, l, mid);
    auto tmp = get(id, l_, r_, v * 2 + 1, mid + 1, r);
    ans.first = min(ans.first, tmp.first);
    ans.second = max(ans.second, tmp.second);
    return ans;
}

int main() {
    int n, k;
    read(n, k);
    int m;
    read(m);
    vc<pair<int, int>> straight, cursed;
    for (int i = 0; i < m; ++i) {
        int l, r;
        read(l, r);
        --l;
        --r;
        if (l <= r) straight.emplace_back(l, r);
        else cursed.emplace_back(l, r);
    }
    vc<pair<int, int>> go(n);
    {// updating for straight
        vc<vc<int>> add(n + 1);
        vc<vc<int>> del(n + 1);
        for (int i = 0; i < straight.size(); ++i) {
            int begin = straight[i].first;
            int end = min(straight[i].second + 1, straight[i].first + k);
            add[begin].push_back(straight[i].second);
            del[end].push_back(straight[i].second);
        }
        for (int i = 0; i < n; ++i) go[i] = {i, i};
        multiset<int> e;
        for (int i = 0; i < n; ++i) {
            for (auto x: del[i]) e.erase(e.find(x));
            for (auto x: add[i]) e.insert(x);
            if (!e.empty()) go[i].second = max(go[i].second, *e.rbegin());
        }
    }
    {// updating for cursed
        vc<vc<int>> add(n + 1);
        vc<vc<int>> del(n + 1);
        for (int i = 0; i < cursed.size(); ++i) {
            int begin = cursed[i].first;
            int end = max(cursed[i].second - 1, cursed[i].first - k);
            add[begin].push_back(cursed[i].second);
            if (end >= 0) del[end].push_back(cursed[i].second);
        }
        multiset<int> e;
        for (int i = n - 1; i >= 0; --i) {
            for (auto x: del[i]) e.erase(e.find(x));
            for (auto x: add[i]) e.insert(x);
            if (!e.empty()) go[i].first = min(go[i].first, *e.begin());
        }
    }
    for (int i = 0; i < n; ++i) {
        up[0][i] = go[i];
    }
    build(0);
    for (int sz = 1; sz < 17; ++sz) {
        for (int v = 0; v < n; ++v) {
            up[sz][v] = get(sz - 1, up[sz - 1][v].first, up[sz - 1][v].second);
        }
        build(sz);
    }

    int q;
    read(q);
    while (q--) {
        int v, to;
        read(v, to);
        --v, --to;
        pair<int, int> nw = {v, v};
        int ans = 0;
        for (int j = 16; j >= 0; --j) {
            auto tmp = get(j, nw.first, nw.second);
            if (!(tmp.first <= to && to <= tmp.second)) nw = tmp, ans += 1 << j;
        }
        if (!(nw.first <= to && to <= nw.second)) {
            auto tmp = get(0, nw.first, nw.second);
            nw = tmp;
            ++ans;
        }
        if (nw.first <= to && to <= nw.second) {
            cout << ans << '\n';
        } else {
            cout << -1 << '\n';
        }
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:285:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  285 |         for (int i = 0; i < straight.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~~~
Main.cpp:302:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  302 |         for (int i = 0; i < cursed.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 70348 KB Output is correct
2 Correct 75 ms 70336 KB Output is correct
3 Correct 67 ms 70288 KB Output is correct
4 Correct 68 ms 70348 KB Output is correct
5 Correct 69 ms 70324 KB Output is correct
6 Correct 70 ms 70472 KB Output is correct
7 Correct 77 ms 70360 KB Output is correct
8 Correct 66 ms 70288 KB Output is correct
9 Correct 70 ms 70388 KB Output is correct
10 Correct 65 ms 70308 KB Output is correct
11 Correct 67 ms 70360 KB Output is correct
12 Correct 70 ms 70348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 70348 KB Output is correct
2 Correct 75 ms 70336 KB Output is correct
3 Correct 67 ms 70288 KB Output is correct
4 Correct 68 ms 70348 KB Output is correct
5 Correct 69 ms 70324 KB Output is correct
6 Correct 70 ms 70472 KB Output is correct
7 Correct 77 ms 70360 KB Output is correct
8 Correct 66 ms 70288 KB Output is correct
9 Correct 70 ms 70388 KB Output is correct
10 Correct 65 ms 70308 KB Output is correct
11 Correct 67 ms 70360 KB Output is correct
12 Correct 70 ms 70348 KB Output is correct
13 Correct 90 ms 70760 KB Output is correct
14 Correct 87 ms 70776 KB Output is correct
15 Correct 79 ms 70776 KB Output is correct
16 Correct 81 ms 70688 KB Output is correct
17 Correct 78 ms 70712 KB Output is correct
18 Correct 80 ms 70728 KB Output is correct
19 Correct 90 ms 70752 KB Output is correct
20 Correct 74 ms 70776 KB Output is correct
21 Correct 73 ms 70872 KB Output is correct
22 Correct 83 ms 70900 KB Output is correct
23 Correct 80 ms 70696 KB Output is correct
24 Correct 100 ms 70676 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 93244 KB Output is correct
2 Correct 461 ms 89112 KB Output is correct
3 Correct 538 ms 93784 KB Output is correct
4 Correct 462 ms 89068 KB Output is correct
5 Correct 533 ms 96544 KB Output is correct
6 Correct 532 ms 97968 KB Output is correct
7 Correct 365 ms 99708 KB Output is correct
8 Correct 373 ms 94188 KB Output is correct
9 Correct 337 ms 94512 KB Output is correct
10 Correct 544 ms 90040 KB Output is correct
11 Correct 481 ms 90608 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 89428 KB Output is correct
2 Correct 694 ms 98404 KB Output is correct
3 Correct 779 ms 94840 KB Output is correct
4 Correct 515 ms 101120 KB Output is correct
5 Correct 608 ms 99384 KB Output is correct
6 Correct 541 ms 99380 KB Output is correct
7 Correct 767 ms 91820 KB Output is correct
8 Correct 725 ms 92928 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 934 ms 94088 KB Output is correct
2 Correct 890 ms 93276 KB Output is correct
3 Correct 910 ms 88744 KB Output is correct
4 Correct 772 ms 86820 KB Output is correct
5 Correct 648 ms 85716 KB Output is correct
6 Correct 686 ms 85284 KB Output is correct
7 Correct 679 ms 95208 KB Output is correct
8 Correct 74 ms 70368 KB Output is correct
9 Correct 79 ms 70752 KB Output is correct
10 Correct 642 ms 96304 KB Output is correct
11 Correct 730 ms 98456 KB Output is correct
12 Correct 785 ms 96512 KB Output is correct
13 Correct 767 ms 98440 KB Output is correct
14 Correct 70 ms 70348 KB Output is correct
15 Correct 79 ms 70692 KB Output is correct
16 Correct 556 ms 93972 KB Output is correct
17 Correct 908 ms 94896 KB Output is correct
18 Correct 823 ms 94852 KB Output is correct
19 Correct 776 ms 94680 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 70348 KB Output is correct
2 Correct 75 ms 70336 KB Output is correct
3 Correct 67 ms 70288 KB Output is correct
4 Correct 68 ms 70348 KB Output is correct
5 Correct 69 ms 70324 KB Output is correct
6 Correct 70 ms 70472 KB Output is correct
7 Correct 77 ms 70360 KB Output is correct
8 Correct 66 ms 70288 KB Output is correct
9 Correct 70 ms 70388 KB Output is correct
10 Correct 65 ms 70308 KB Output is correct
11 Correct 67 ms 70360 KB Output is correct
12 Correct 70 ms 70348 KB Output is correct
13 Correct 90 ms 70760 KB Output is correct
14 Correct 87 ms 70776 KB Output is correct
15 Correct 79 ms 70776 KB Output is correct
16 Correct 81 ms 70688 KB Output is correct
17 Correct 78 ms 70712 KB Output is correct
18 Correct 80 ms 70728 KB Output is correct
19 Correct 90 ms 70752 KB Output is correct
20 Correct 74 ms 70776 KB Output is correct
21 Correct 73 ms 70872 KB Output is correct
22 Correct 83 ms 70900 KB Output is correct
23 Correct 80 ms 70696 KB Output is correct
24 Correct 100 ms 70676 KB Output is correct
25 Correct 496 ms 93244 KB Output is correct
26 Correct 461 ms 89112 KB Output is correct
27 Correct 538 ms 93784 KB Output is correct
28 Correct 462 ms 89068 KB Output is correct
29 Correct 533 ms 96544 KB Output is correct
30 Correct 532 ms 97968 KB Output is correct
31 Correct 365 ms 99708 KB Output is correct
32 Correct 373 ms 94188 KB Output is correct
33 Correct 337 ms 94512 KB Output is correct
34 Correct 544 ms 90040 KB Output is correct
35 Correct 481 ms 90608 KB Output is correct
36 Correct 639 ms 89428 KB Output is correct
37 Correct 694 ms 98404 KB Output is correct
38 Correct 779 ms 94840 KB Output is correct
39 Correct 515 ms 101120 KB Output is correct
40 Correct 608 ms 99384 KB Output is correct
41 Correct 541 ms 99380 KB Output is correct
42 Correct 767 ms 91820 KB Output is correct
43 Correct 725 ms 92928 KB Output is correct
44 Correct 934 ms 94088 KB Output is correct
45 Correct 890 ms 93276 KB Output is correct
46 Correct 910 ms 88744 KB Output is correct
47 Correct 772 ms 86820 KB Output is correct
48 Correct 648 ms 85716 KB Output is correct
49 Correct 686 ms 85284 KB Output is correct
50 Correct 679 ms 95208 KB Output is correct
51 Correct 74 ms 70368 KB Output is correct
52 Correct 79 ms 70752 KB Output is correct
53 Correct 642 ms 96304 KB Output is correct
54 Correct 730 ms 98456 KB Output is correct
55 Correct 785 ms 96512 KB Output is correct
56 Correct 767 ms 98440 KB Output is correct
57 Correct 70 ms 70348 KB Output is correct
58 Correct 79 ms 70692 KB Output is correct
59 Correct 556 ms 93972 KB Output is correct
60 Correct 908 ms 94896 KB Output is correct
61 Correct 823 ms 94852 KB Output is correct
62 Correct 776 ms 94680 KB Output is correct
63 Correct 796 ms 94356 KB Output is correct
64 Correct 900 ms 94916 KB Output is correct
65 Correct 825 ms 94488 KB Output is correct
66 Correct 751 ms 92532 KB Output is correct
67 Correct 760 ms 94104 KB Output is correct
68 Correct 605 ms 97512 KB Output is correct
69 Correct 579 ms 99392 KB Output is correct
70 Correct 741 ms 92116 KB Output is correct
71 Correct 882 ms 97740 KB Output is correct