oj.uz

Submission #829508

# Submission time Handle Problem Language Result Execution time Memory
829508 2023-08-18T11:40:56 Z green_gold_dog Railway Trip 2 (JOI22_ho_t4) C++17
100 / 100
 1345 ms 61344 KB 
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,abm,popcnt,mmx")
#include <bits/stdc++.h>

using namespace std;

typedef int ll;
typedef double db;
typedef long double ldb;
typedef complex<double> cd;

constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007, LOG = 18;
constexpr db PI = acos(-1);
constexpr bool IS_FILE = false, IS_TEST_CASES = false;

random_device rd;
mt19937 rnd32(rd());
mt19937_64 rnd64(rd());

template<typename T>
bool assign_max(T& a, T b) {
        if (b > a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
bool assign_min(T& a, T b) {
        if (b < a) {
                a = b;
                return true;
        }
        return false;
}

template<typename T>
T square(T a) {
        return a * a;
}

template<>
struct std::hash<pair<ll, ll>> {
        ll operator() (pair<ll, ll> p) const {
                return ((__int128)p.first * MOD + p.second) % INF64;
        }
};

struct segment_tree_min {
        vector<ll> tree;
        ll size;
        segment_tree_min(vector<ll> arr) {
                size = 1;
                while (size < arr.size()) {
                        size *= 2;
                }
                tree.resize(size * 2, 0);
                arr.resize(size, 0);
                build(1, 0, size, arr);
        }
        void build(ll v, ll l, ll r, vector<ll>& arr) {
                if (r - l == 1) {
                        tree[v] = arr[l];
                        return;
                }
                ll mid = (l + r) / 2;
                build(v * 2, l, mid, arr);
                build(v * 2 + 1, mid, r, arr);
                tree[v] = min(tree[v * 2], tree[v * 2 + 1]);
        }
        ll get(ll l, ll r) {
                r++;
                return get(1, 0, size, l, r);
        }
        ll get(ll v, ll l, ll r, ll ql, ll qr) {
                if (ql <= l && r <= qr) {
                        return tree[v];
                }
                if (qr <= l || r <= ql) {
                        return INF32;
                }
                ll mid = (l + r) / 2;
                return min(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr));
        }
};

struct segment_tree_max {
        vector<ll> tree;
        ll size;
        segment_tree_max(vector<ll> arr) {
                size = 1;
                while (size < arr.size()) {
                        size *= 2;
                }
                tree.resize(size * 2, 0);
                arr.resize(size, 0);
                build(1, 0, size, arr);
        }
        void build(ll v, ll l, ll r, vector<ll>& arr) {
                if (r - l == 1) {
                        tree[v] = arr[l];
                        return;
                }
                ll mid = (l + r) / 2;
                build(v * 2, l, mid, arr);
                build(v * 2 + 1, mid, r, arr);
                tree[v] = max(tree[v * 2], tree[v * 2 + 1]);
        }
        ll get(ll l, ll r) {
                r++;
                return get(1, 0, size, l, r);
        }
        ll get(ll v, ll l, ll r, ll ql, ll qr) {
                if (ql <= l && r <= qr) {
                        return tree[v];
                }
                if (qr <= l || r <= ql) {
                        return 0;
                }
                ll mid = (l + r) / 2;
                return max(get(v * 2, l, mid, ql, qr), get(v * 2 + 1, mid, r, ql, qr));
        }
};

void solve() {
        ll n, k, m;
        cin >> n >> k >> m;
        vector<vector<pair<ll, bool>>> ami(n + 1), ama(n + 1);
        vector<pair<ll, ll>> arr(m);
        for (ll i = 0; i < m; i++) {
                cin >> arr[i].first >> arr[i].second;
                arr[i].first--;
                arr[i].second--;
                if (arr[i].first < arr[i].second) {
                        ama[arr[i].first].emplace_back(arr[i].second, true);
                        ama[min(arr[i].second, arr[i].first + k)].emplace_back(arr[i].second, false);
                } else {
                        ami[max(arr[i].second, arr[i].first - k + 1)].emplace_back(arr[i].second, true);
                        ami[arr[i].first + 1].emplace_back(arr[i].second, false);
                }
        }
        multiset<ll> mi, ma;
        vector<ll> ls, rs;
        for (ll i = 0; i < n; i++) {
                mi.insert(i);
                ma.insert(i);
                for (auto[j, b] : ama[i]) {
                        if (b) {
                                ma.insert(j);
                        } else {
                                ma.erase(ma.find(j));
                        }
                }
                for (auto[j, b] : ami[i]) {
                        if (b) {
                                mi.insert(j);
                        } else {
                                mi.erase(mi.find(j));
                        }
                }
                ls.push_back(*mi.begin());
                rs.push_back(*ma.rbegin());
                mi.erase(mi.find(i));
                ma.erase(ma.find(i));
        }
        vector<ll> p2l = ls, p2r = rs;
        vector<segment_tree_min> p2mi(1, segment_tree_min(ls));
        vector<segment_tree_max> p2ma(1, segment_tree_max(rs));
        for (ll i = 0; i < LOG; i++) {
                vector<ll> nl, nr;
                for (ll j = 0; j < n; j++) {
                        nl.push_back(p2mi.back().get(p2l[j], p2r[j]));
                        nr.push_back(p2ma.back().get(p2l[j], p2r[j]));
                }
                p2l = nl;
                p2r = nr;
                p2mi.emplace_back(nl);
                p2ma.emplace_back(nr);
        }
        ll q;
        cin >> q;
        for (ll i = 0; i < q; i++) {
                ll ans = 1;
                ll s, t;
                cin >> s >> t;
                s--;
                t--;
                pair<ll, ll> no = make_pair(s, s);
                for (ll j = LOG; j >= 0; j--) {
                        if (p2mi[j].get(no.first, no.second) > t || p2ma[j].get(no.first, no.second) < t) {
                                ans += (1 << j);
                                no = make_pair(p2mi[j].get(no.first, no.second), p2ma[j].get(no.first, no.second));
                        }
                }
                if (ans > n) {
                        cout << -1 << '\n';
                } else {
                        cout << ans << '\n';
                }
        }
}

int main() {
        if (IS_FILE) {
                freopen("", "r", stdin);
                freopen("", "w", stdout);
        }
        ios_base::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        ll t = 1;
        if (IS_TEST_CASES) {
                cin >> t;
        }
        for (ll i = 0; i < t; i++) {
                solve();
        }
}

Compilation message

Main.cpp:12:22: warning: overflow in conversion from 'long int' to 'll' {aka 'int'} changes value from '9000000000000000000' to '-494665728' [-Woverflow]
   12 | constexpr ll INF64 = 9'000'000'000'000'000'000, INF32 = 2'000'000'000, MOD = 1'000'000'007, LOG = 18;
      |                      ^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp: In constructor 'segment_tree_min::segment_tree_min(std::vector<int>)':
Main.cpp:55:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |                 while (size < arr.size()) {
      |                        ~~~~~^~~~~~~~~~~~
Main.cpp: In constructor 'segment_tree_max::segment_tree_max(std::vector<int>)':
Main.cpp:93:29: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |                 while (size < arr.size()) {
      |                        ~~~~~^~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:206:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |                 freopen("", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~
Main.cpp:207:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  207 |                 freopen("", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 14 ms 1236 KB Output is correct
14 Correct 15 ms 1212 KB Output is correct
15 Correct 8 ms 1108 KB Output is correct
16 Correct 12 ms 1236 KB Output is correct
17 Correct 14 ms 1240 KB Output is correct
18 Correct 12 ms 1264 KB Output is correct
19 Correct 12 ms 1272 KB Output is correct
20 Correct 8 ms 1264 KB Output is correct
21 Correct 7 ms 1236 KB Output is correct
22 Correct 17 ms 1252 KB Output is correct
23 Correct 16 ms 1236 KB Output is correct
24 Correct 13 ms 1168 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 51564 KB Output is correct
2 Correct 561 ms 51700 KB Output is correct
3 Correct 587 ms 51884 KB Output is correct
4 Correct 589 ms 51376 KB Output is correct
5 Correct 537 ms 58708 KB Output is correct
6 Correct 559 ms 58088 KB Output is correct
7 Correct 315 ms 59952 KB Output is correct
8 Correct 301 ms 55684 KB Output is correct
9 Correct 299 ms 55216 KB Output is correct
10 Correct 564 ms 58916 KB Output is correct
11 Correct 496 ms 58960 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 710 ms 53876 KB Output is correct
2 Correct 860 ms 59484 KB Output is correct
3 Correct 1022 ms 55392 KB Output is correct
4 Correct 485 ms 60664 KB Output is correct
5 Correct 551 ms 60480 KB Output is correct
6 Correct 521 ms 60428 KB Output is correct
7 Correct 818 ms 59664 KB Output is correct
8 Correct 802 ms 59664 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1110 ms 58796 KB Output is correct
2 Correct 1205 ms 54032 KB Output is correct
3 Correct 1031 ms 51508 KB Output is correct
4 Correct 1026 ms 49800 KB Output is correct
5 Correct 818 ms 49252 KB Output is correct
6 Correct 852 ms 48736 KB Output is correct
7 Correct 678 ms 55220 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 11 ms 1236 KB Output is correct
10 Correct 594 ms 59364 KB Output is correct
11 Correct 720 ms 59984 KB Output is correct
12 Correct 803 ms 59216 KB Output is correct
13 Correct 752 ms 59476 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 14 ms 1208 KB Output is correct
16 Correct 589 ms 58188 KB Output is correct
17 Correct 1063 ms 58940 KB Output is correct
18 Correct 975 ms 59128 KB Output is correct
19 Correct 941 ms 58868 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 468 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 2 ms 468 KB Output is correct
13 Correct 14 ms 1236 KB Output is correct
14 Correct 15 ms 1212 KB Output is correct
15 Correct 8 ms 1108 KB Output is correct
16 Correct 12 ms 1236 KB Output is correct
17 Correct 14 ms 1240 KB Output is correct
18 Correct 12 ms 1264 KB Output is correct
19 Correct 12 ms 1272 KB Output is correct
20 Correct 8 ms 1264 KB Output is correct
21 Correct 7 ms 1236 KB Output is correct
22 Correct 17 ms 1252 KB Output is correct
23 Correct 16 ms 1236 KB Output is correct
24 Correct 13 ms 1168 KB Output is correct
25 Correct 606 ms 51564 KB Output is correct
26 Correct 561 ms 51700 KB Output is correct
27 Correct 587 ms 51884 KB Output is correct
28 Correct 589 ms 51376 KB Output is correct
29 Correct 537 ms 58708 KB Output is correct
30 Correct 559 ms 58088 KB Output is correct
31 Correct 315 ms 59952 KB Output is correct
32 Correct 301 ms 55684 KB Output is correct
33 Correct 299 ms 55216 KB Output is correct
34 Correct 564 ms 58916 KB Output is correct
35 Correct 496 ms 58960 KB Output is correct
36 Correct 710 ms 53876 KB Output is correct
37 Correct 860 ms 59484 KB Output is correct
38 Correct 1022 ms 55392 KB Output is correct
39 Correct 485 ms 60664 KB Output is correct
40 Correct 551 ms 60480 KB Output is correct
41 Correct 521 ms 60428 KB Output is correct
42 Correct 818 ms 59664 KB Output is correct
43 Correct 802 ms 59664 KB Output is correct
44 Correct 1110 ms 58796 KB Output is correct
45 Correct 1205 ms 54032 KB Output is correct
46 Correct 1031 ms 51508 KB Output is correct
47 Correct 1026 ms 49800 KB Output is correct
48 Correct 818 ms 49252 KB Output is correct
49 Correct 852 ms 48736 KB Output is correct
50 Correct 678 ms 55220 KB Output is correct
51 Correct 2 ms 468 KB Output is correct
52 Correct 11 ms 1236 KB Output is correct
53 Correct 594 ms 59364 KB Output is correct
54 Correct 720 ms 59984 KB Output is correct
55 Correct 803 ms 59216 KB Output is correct
56 Correct 752 ms 59476 KB Output is correct
57 Correct 2 ms 468 KB Output is correct
58 Correct 14 ms 1208 KB Output is correct
59 Correct 589 ms 58188 KB Output is correct
60 Correct 1063 ms 58940 KB Output is correct
61 Correct 975 ms 59128 KB Output is correct
62 Correct 941 ms 58868 KB Output is correct
63 Correct 992 ms 53152 KB Output is correct
64 Correct 1345 ms 53668 KB Output is correct
65 Correct 1141 ms 53148 KB Output is correct
66 Correct 725 ms 61068 KB Output is correct
67 Correct 982 ms 58888 KB Output is correct
68 Correct 658 ms 60084 KB Output is correct
69 Correct 590 ms 61344 KB Output is correct
70 Correct 1111 ms 59584 KB Output is correct
71 Correct 989 ms 59684 KB Output is correct