Submission #593817

#	Time	Username	Problem	Language	Result	Execution time	Memory
593817		vovik	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	934 ms	101120 KiB

Main

#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 (stderr)

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 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13