oj.uz

Submission #746081

# Submission time Handle Problem Language Result Execution time Memory
746081 2023-05-21T11:26:44 Z nguyentunglam Railway Trip 2 (JOI22_ho_t4) C++17
100 / 100
 837 ms 67212 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
int l[20][N], r[20][N];
int n, m, k;
vector<pair<int, int> > edge[N];

struct IT {
    int f[N << 2], g[N << 2];

    void build(int s, int l, int r) {
        if (l == r) {
            f[s] = g[s] = l;
            return;
        }
        int mid = l + r >> 1;
        build(s << 1, l, mid);
        build(s << 1 | 1, mid + 1, r);
        f[s] = min(f[s << 1], f[s << 1 | 1]);
        g[s] = max(g[s << 1], g[s << 1 | 1]);
    }

    void up(int s, int l, int r, int pos, int val1, int val2) {
        if (l == r) {
            f[s] = val1; g[s] = val2;
            return;
        }
        int mid = l + r >> 1;
        if (pos <= mid) up(s << 1, l, mid, pos, val1, val2);
        else up(s << 1 | 1, mid + 1, r, pos, val1, val2);
        f[s] = min(f[s << 1], f[s << 1 | 1]);
        g[s] = max(g[s << 1], g[s << 1 | 1]);
    }

    pair<int, int> get(int s, int l, int r, int from, int to) {
        if (l > to || r < from) return {1e9, 0};
        if (from <= l && r <= to) return make_pair(f[s], g[s]);
        int mid = l + r >> 1;
        int a, b, c, d;
        tie(a, b) = get(s << 1, l, mid, from, to);
        tie(c, d) = get(s << 1 | 1, mid + 1, r, from, to);
        return make_pair(min(a, c), max(b, d));
    }
} it[20];

int main() {
    #define task ""
    cin.tie(0) -> sync_with_stdio(0);
    if (fopen ("task.inp", "r")) {
        freopen ("task.inp", "r", stdin);
        freopen ("task.out", "w", stdout);
    }
    if (fopen (task".inp", "r")) {
        freopen (task".inp", "r", stdin);
        freopen (task".out", "w", stdout);
    }
    cin >> n >> k >> m;
    set<int> s1, s2;
    for(int i = 1; i <= n; i++) l[0][i] = r[0][i] = i, s1.insert(i), s2.insert(i);
    s1.insert(n + 1);
    s2.insert(n + 1);
    for(int i = 1; i <= m; i++) {
        int a, b; cin >> a >> b;
        int from, to;
        if (a < b) {
            from = a; to = min(a + k - 1, b - 1);
        }
        else {
            from = max(a - k + 1, b + 1); to = a;
        }
        edge[b].emplace_back(from, to);
    }

    for(int val = 1; val <= n; val++) {
        for(auto &[from, to] : edge[val]) {
            while (!s1.empty()) {
                auto pos = *s1.lower_bound(from);
                if (pos > to) break;
                l[0][pos] = min(l[0][pos], val);
                s1.erase(pos);
            }
        }
    }

    for(int val = n; val >= 1; val--) {
        for(auto &[from, to] : edge[val]) {
            while (!s2.empty()) {
                auto pos = *s2.lower_bound(from);
                if (pos > to) break;
                r[0][pos] = max(r[0][pos], val);
//                if (pos == 1) cout << from << " " << to << " " << val << endl;
                s2.erase(pos);
            }
        }
    }

    int lg = log2(n);
    for(int j = 0; j <= lg; j++) it[j].build(1, 1, n);
    for(int i = 1; i <= n; i++) it[0].up(1, 1, n, i, l[0][i], r[0][i]);


    for(int j = 1; j <= lg; j++) for(int i = 1; i <= n; i++) {
        tie(l[j][i], r[j][i]) = it[j - 1].get(1, 1, n, l[j - 1][i], r[j - 1][i]);
        it[j].up(1, 1, n, i, l[j][i], r[j][i]);
    }
    int q; cin >> q;
    while (q--) {
        int s, t; cin >> s >> t;
        int left = s, right = s, ans = 0;
        for(int j = lg; j >= 0; j--) {
            int ll, rr;
            tie(ll, rr) = it[j].get(1, 1, n, left, right);
            if (t > rr || t < ll) {
                left = ll; right = rr;
                ans += (1 << j);
            }
        }
        if (ans == (1 << lg << 1) - 1) ans = -2;
        cout << ans + 1 << endl;
    }
}

Compilation message

Main.cpp: In member function 'void IT::build(int, int, int)':
Main.cpp:20:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'void IT::up(int, int, int, int, int, int)':
Main.cpp:32:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In member function 'std::pair<int, int> IT::get(int, int, int, int, int)':
Main.cpp:42:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int mid = l + r >> 1;
      |                   ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:54:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen ("task.inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:55:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen ("task.out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:58:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen (task".inp", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:59:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         freopen (task".out", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 2 ms 2900 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2900 KB Output is correct
12 Correct 2 ms 2900 KB Output is correct
13 Correct 9 ms 3712 KB Output is correct
14 Correct 8 ms 3668 KB Output is correct
15 Correct 6 ms 3668 KB Output is correct
16 Correct 7 ms 3696 KB Output is correct
17 Correct 9 ms 3668 KB Output is correct
18 Correct 5 ms 3668 KB Output is correct
19 Correct 8 ms 3668 KB Output is correct
20 Correct 6 ms 3720 KB Output is correct
21 Correct 5 ms 3668 KB Output is correct
22 Correct 8 ms 3720 KB Output is correct
23 Correct 9 ms 3668 KB Output is correct
24 Correct 8 ms 3732 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 542 ms 63208 KB Output is correct
2 Correct 526 ms 63724 KB Output is correct
3 Correct 593 ms 64484 KB Output is correct
4 Correct 545 ms 63544 KB Output is correct
5 Correct 325 ms 66132 KB Output is correct
6 Correct 550 ms 65836 KB Output is correct
7 Correct 272 ms 64200 KB Output is correct
8 Correct 297 ms 63596 KB Output is correct
9 Correct 269 ms 63640 KB Output is correct
10 Correct 516 ms 66304 KB Output is correct
11 Correct 487 ms 66252 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 626 ms 64488 KB Output is correct
2 Correct 569 ms 66952 KB Output is correct
3 Correct 757 ms 65520 KB Output is correct
4 Correct 379 ms 64680 KB Output is correct
5 Correct 393 ms 66660 KB Output is correct
6 Correct 395 ms 66736 KB Output is correct
7 Correct 674 ms 66880 KB Output is correct
8 Correct 702 ms 67052 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 642 ms 66788 KB Output is correct
2 Correct 837 ms 65604 KB Output is correct
3 Correct 815 ms 63272 KB Output is correct
4 Correct 767 ms 62100 KB Output is correct
5 Correct 664 ms 61296 KB Output is correct
6 Correct 662 ms 61132 KB Output is correct
7 Correct 521 ms 63120 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 8 ms 3732 KB Output is correct
10 Correct 471 ms 66216 KB Output is correct
11 Correct 542 ms 66620 KB Output is correct
12 Correct 556 ms 66524 KB Output is correct
13 Correct 571 ms 66764 KB Output is correct
14 Correct 2 ms 2900 KB Output is correct
15 Correct 10 ms 3736 KB Output is correct
16 Correct 571 ms 66184 KB Output is correct
17 Correct 805 ms 67212 KB Output is correct
18 Correct 766 ms 67024 KB Output is correct
19 Correct 741 ms 67144 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2900 KB Output is correct
2 Correct 3 ms 2900 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 2900 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 2 ms 2900 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 2 ms 2900 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2900 KB Output is correct
12 Correct 2 ms 2900 KB Output is correct
13 Correct 9 ms 3712 KB Output is correct
14 Correct 8 ms 3668 KB Output is correct
15 Correct 6 ms 3668 KB Output is correct
16 Correct 7 ms 3696 KB Output is correct
17 Correct 9 ms 3668 KB Output is correct
18 Correct 5 ms 3668 KB Output is correct
19 Correct 8 ms 3668 KB Output is correct
20 Correct 6 ms 3720 KB Output is correct
21 Correct 5 ms 3668 KB Output is correct
22 Correct 8 ms 3720 KB Output is correct
23 Correct 9 ms 3668 KB Output is correct
24 Correct 8 ms 3732 KB Output is correct
25 Correct 542 ms 63208 KB Output is correct
26 Correct 526 ms 63724 KB Output is correct
27 Correct 593 ms 64484 KB Output is correct
28 Correct 545 ms 63544 KB Output is correct
29 Correct 325 ms 66132 KB Output is correct
30 Correct 550 ms 65836 KB Output is correct
31 Correct 272 ms 64200 KB Output is correct
32 Correct 297 ms 63596 KB Output is correct
33 Correct 269 ms 63640 KB Output is correct
34 Correct 516 ms 66304 KB Output is correct
35 Correct 487 ms 66252 KB Output is correct
36 Correct 626 ms 64488 KB Output is correct
37 Correct 569 ms 66952 KB Output is correct
38 Correct 757 ms 65520 KB Output is correct
39 Correct 379 ms 64680 KB Output is correct
40 Correct 393 ms 66660 KB Output is correct
41 Correct 395 ms 66736 KB Output is correct
42 Correct 674 ms 66880 KB Output is correct
43 Correct 702 ms 67052 KB Output is correct
44 Correct 642 ms 66788 KB Output is correct
45 Correct 837 ms 65604 KB Output is correct
46 Correct 815 ms 63272 KB Output is correct
47 Correct 767 ms 62100 KB Output is correct
48 Correct 664 ms 61296 KB Output is correct
49 Correct 662 ms 61132 KB Output is correct
50 Correct 521 ms 63120 KB Output is correct
51 Correct 2 ms 2900 KB Output is correct
52 Correct 8 ms 3732 KB Output is correct
53 Correct 471 ms 66216 KB Output is correct
54 Correct 542 ms 66620 KB Output is correct
55 Correct 556 ms 66524 KB Output is correct
56 Correct 571 ms 66764 KB Output is correct
57 Correct 2 ms 2900 KB Output is correct
58 Correct 10 ms 3736 KB Output is correct
59 Correct 571 ms 66184 KB Output is correct
60 Correct 805 ms 67212 KB Output is correct
61 Correct 766 ms 67024 KB Output is correct
62 Correct 741 ms 67144 KB Output is correct
63 Correct 755 ms 64308 KB Output is correct
64 Correct 823 ms 65024 KB Output is correct
65 Correct 832 ms 64436 KB Output is correct
66 Correct 334 ms 66872 KB Output is correct
67 Correct 824 ms 66652 KB Output is correct
68 Correct 555 ms 66840 KB Output is correct
69 Correct 425 ms 66692 KB Output is correct
70 Correct 720 ms 67084 KB Output is correct
71 Correct 789 ms 67200 KB Output is correct