oj.uz

Submission #673261

# Submission time Handle Problem Language Result Execution time Memory
673261 2022-12-20T03:59:34 Z Cyanmond Discharging (NOI20_discharging) C++17
100 / 100
 931 ms 248720 KB 
#include <bits/stdc++.h>

using i64 = long long;
constexpr i64 inf = 1ll << 60;

class SparseTable {
    int n;
    std::vector<int> log_table;
    std::vector<std::vector<i64>> data;

  public:
    SparseTable(std::vector<i64> vec) : n(vec.size()) {
        log_table.assign(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            log_table[i] = std::max(log_table[i], log_table[i - 1]);
            if (2 * i <= n) {
                log_table[2 * i] = log_table[i] + 1;
            }
        }

        data.resize(log_table[n] + 1);
        data[0] = vec;
        for (int d = 1; d <= log_table[n]; ++d) {
            const int w = 1 << d;
            data[d].resize(n - w + 1);
            for (int i = 0; i + w <= n; ++i) {
                data[d][i] = std::max(data[d - 1][i], data[d - 1][i + w / 2]);
            }
        }
    }

    i64 fold(int l, int r) const {
        const int w = r - l;
        const int d = log_table[w];
        return std::max(data[d][l], data[d][r - (1 << d)]);
    }
};

class SegmentTree {
    int n, size;
    std::vector<i64> data;

  public:
    SegmentTree(int n_) : n(n_) {
        size = 1;
        while (size < n) {
            size *= 2;
        }
        data.assign(2 * size, inf);
    }

    void set(int i, i64 v) {
        i += size;
        data[i] = v;
        while (i != 1) {
            i /= 2;
            data[i] = std::min(data[2 * i], data[2 * i + 1]);
        }
    }

    i64 fold(int l, int r) {
        i64 ret = inf;
        for (l += size, r += size; l < r; l /= 2, r /= 2) {
            if (l % 2 == 1) {
                ret = std::min(ret, data[l++]);
            }
            if (r % 2 == 1) {
                ret = std::min(ret, data[--r]);
            }
        }
        return ret;
    }
};

class LiChaoTree {
    struct Line {
        i64 a, b;
        i64 get(i64 x) const {
            return a * x + b;
        }
    }; 

    int n, seg_size;
    std::vector<Line> data;
    std::stack<std::tuple<int, int, Line, Line>> stk;

  public:
    LiChaoTree(int n_) : n(n_) {
        seg_size = 1;
        while (seg_size < n) {
            seg_size *= 2;
        }
        data.assign(2 * seg_size, {0, inf});
    }

    void update(int id, const Line &x) {
        update(id, x, 1, 0, seg_size);
    }

    void rollback(int lm) {
        while (not stk.empty()) {
            const auto [id, i, pv, nw] = stk.top();
            if (lm > id) {
                break;
            }
            stk.pop();
            data[i] = pv;
        }
    }

    i64 get(int x) {
        int xi = x;
        xi += seg_size;
        i64 res = inf;
        while (xi != 0) {
            res = std::min(res, data[xi].get(x));
            xi /= 2;
        }
        return res;
    }

  private:
    void update(int id, Line x, int k, int l, int r) {
        const int m = (l + r) / 2;
        bool l_over = data[k].get(l) > x.get(l), r_over = data[k].get(r - 1) > x.get(r - 1);
        if (l_over == r_over) {
            if (l_over) {
                stk.push({id, k, data[k], x});
                data[k] = x;
            }
            return;
        }
        bool m_over = data[k].get(m) > x.get(m);
        if (m_over) {
            stk.push({id, k, data[k], x});
            std::swap(data[k], x);
            if (not l_over) {
                update(id, x, 2 * k, l, m);
            }
            if (not r_over) {
                update(id, x, 2 * k + 1, m, r);
            }
            return;
        }
        if (l_over) {
            update(id, x, 2 * k, l, m);
        }
        if (r_over) {
            update(id, x, 2 * k + 1, m, r);
        }
    }
};

int main() {
    int N;
    std::cin >> N;
    std::vector<i64> T(N);
    for (auto &e : T) {
        std::cin >> e;
    }
    T.push_back(0);
    std::reverse(T.begin(), T.end());
    const auto st = SparseTable(T);

    SegmentTree dp(N + 1);
    dp.set(0, 0);
    LiChaoTree tree(N + 1);
    tree.update(0, {0, 0});
    for (int i = 1; i <= N; ++i) {
        int l = -1, r = i;
        while (r - l > 1) {
            const auto mid = (l + r) / 2;
            if (st.fold(mid, i) > T[i]) {
                l = mid;
            } else {
                r = mid;
            }
        }
        tree.rollback(r);
        tree.update(i, {T[i], dp.fold(l == -1 ? 0 : l, i)});
        dp.set(i, tree.get(i));
    }

    std::cout << dp.fold(N, N + 1) << std::endl;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 564 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 604 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 564 KB Output is correct
11 Correct 2 ms 468 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 718 ms 243440 KB Output is correct
17 Correct 744 ms 244784 KB Output is correct
18 Correct 730 ms 239764 KB Output is correct
19 Correct 746 ms 244168 KB Output is correct
20 Correct 759 ms 245648 KB Output is correct
21 Correct 756 ms 245304 KB Output is correct
22 Correct 767 ms 243608 KB Output is correct
23 Correct 771 ms 247228 KB Output is correct
24 Correct 861 ms 247456 KB Output is correct
25 Correct 757 ms 247220 KB Output is correct
26 Correct 791 ms 247020 KB Output is correct
27 Correct 740 ms 243144 KB Output is correct
28 Correct 761 ms 245712 KB Output is correct
29 Correct 780 ms 248636 KB Output is correct
30 Correct 783 ms 248720 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 793 ms 217508 KB Output is correct
2 Correct 803 ms 217472 KB Output is correct
3 Correct 815 ms 217500 KB Output is correct
4 Correct 801 ms 217496 KB Output is correct
5 Correct 803 ms 217652 KB Output is correct
6 Correct 831 ms 217516 KB Output is correct
7 Correct 799 ms 217568 KB Output is correct
8 Correct 803 ms 217396 KB Output is correct
9 Correct 823 ms 217560 KB Output is correct
10 Correct 804 ms 217516 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 564 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 1 ms 468 KB Output is correct
31 Correct 2 ms 432 KB Output is correct
32 Correct 1 ms 428 KB Output is correct
33 Correct 2 ms 428 KB Output is correct
34 Correct 1 ms 428 KB Output is correct
35 Correct 1 ms 468 KB Output is correct
36 Correct 1 ms 468 KB Output is correct
37 Correct 2 ms 432 KB Output is correct
38 Correct 2 ms 468 KB Output is correct
39 Correct 1 ms 468 KB Output is correct
40 Correct 1 ms 468 KB Output is correct
41 Correct 1 ms 436 KB Output is correct
42 Correct 1 ms 468 KB Output is correct
43 Correct 1 ms 556 KB Output is correct
44 Correct 2 ms 428 KB Output is correct
45 Correct 2 ms 468 KB Output is correct
46 Correct 2 ms 432 KB Output is correct
47 Correct 1 ms 468 KB Output is correct
48 Correct 2 ms 468 KB Output is correct
49 Correct 2 ms 468 KB Output is correct
50 Correct 1 ms 468 KB Output is correct

Subtask #6
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 596 KB Output is correct
17 Correct 1 ms 596 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 1 ms 596 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 564 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 596 KB Output is correct
27 Correct 1 ms 596 KB Output is correct
28 Correct 1 ms 596 KB Output is correct
29 Correct 2 ms 604 KB Output is correct
30 Correct 718 ms 243440 KB Output is correct
31 Correct 744 ms 244784 KB Output is correct
32 Correct 730 ms 239764 KB Output is correct
33 Correct 746 ms 244168 KB Output is correct
34 Correct 759 ms 245648 KB Output is correct
35 Correct 756 ms 245304 KB Output is correct
36 Correct 767 ms 243608 KB Output is correct
37 Correct 771 ms 247228 KB Output is correct
38 Correct 861 ms 247456 KB Output is correct
39 Correct 757 ms 247220 KB Output is correct
40 Correct 791 ms 247020 KB Output is correct
41 Correct 740 ms 243144 KB Output is correct
42 Correct 761 ms 245712 KB Output is correct
43 Correct 780 ms 248636 KB Output is correct
44 Correct 783 ms 248720 KB Output is correct
45 Correct 793 ms 217508 KB Output is correct
46 Correct 803 ms 217472 KB Output is correct
47 Correct 815 ms 217500 KB Output is correct
48 Correct 801 ms 217496 KB Output is correct
49 Correct 803 ms 217652 KB Output is correct
50 Correct 831 ms 217516 KB Output is correct
51 Correct 799 ms 217568 KB Output is correct
52 Correct 803 ms 217396 KB Output is correct
53 Correct 823 ms 217560 KB Output is correct
54 Correct 804 ms 217516 KB Output is correct
55 Correct 1 ms 468 KB Output is correct
56 Correct 2 ms 432 KB Output is correct
57 Correct 1 ms 428 KB Output is correct
58 Correct 2 ms 428 KB Output is correct
59 Correct 1 ms 428 KB Output is correct
60 Correct 1 ms 468 KB Output is correct
61 Correct 1 ms 468 KB Output is correct
62 Correct 2 ms 432 KB Output is correct
63 Correct 2 ms 468 KB Output is correct
64 Correct 1 ms 468 KB Output is correct
65 Correct 1 ms 468 KB Output is correct
66 Correct 1 ms 436 KB Output is correct
67 Correct 1 ms 468 KB Output is correct
68 Correct 1 ms 556 KB Output is correct
69 Correct 2 ms 428 KB Output is correct
70 Correct 2 ms 468 KB Output is correct
71 Correct 2 ms 432 KB Output is correct
72 Correct 1 ms 468 KB Output is correct
73 Correct 2 ms 468 KB Output is correct
74 Correct 2 ms 468 KB Output is correct
75 Correct 1 ms 468 KB Output is correct
76 Correct 798 ms 223520 KB Output is correct
77 Correct 784 ms 223520 KB Output is correct
78 Correct 773 ms 222916 KB Output is correct
79 Correct 803 ms 223200 KB Output is correct
80 Correct 822 ms 223784 KB Output is correct
81 Correct 775 ms 223132 KB Output is correct
82 Correct 770 ms 223052 KB Output is correct
83 Correct 797 ms 223508 KB Output is correct
84 Correct 781 ms 223272 KB Output is correct
85 Correct 795 ms 223536 KB Output is correct
86 Correct 775 ms 222864 KB Output is correct
87 Correct 766 ms 222892 KB Output is correct
88 Correct 791 ms 223188 KB Output is correct
89 Correct 787 ms 223116 KB Output is correct
90 Correct 781 ms 222996 KB Output is correct
91 Correct 809 ms 222712 KB Output is correct
92 Correct 786 ms 245272 KB Output is correct
93 Correct 901 ms 245544 KB Output is correct
94 Correct 931 ms 222392 KB Output is correct
95 Correct 853 ms 223840 KB Output is correct
96 Correct 821 ms 222736 KB Output is correct
97 Correct 830 ms 223064 KB Output is correct
98 Correct 801 ms 223236 KB Output is correct
99 Correct 792 ms 222904 KB Output is correct
100 Correct 767 ms 222868 KB Output is correct