oj.uz

Submission #501930

# Submission time Handle Problem Language Result Execution time Memory
501930 2022-01-04T19:40:44 Z nighty Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
77 / 100
 3000 ms 38632 KB 
#include <bits/stdc++.h>

using namespace std;

int calcMaxInv(vector<int>& a, int l, int r) {
    int maxVal = 0, res = 0;
    for (int i = l; i <= r; ++i) {
        if (maxVal > a[i]) {
            res = max(res, maxVal + a[i]);
        }
        maxVal = max(maxVal, a[i]);
    }
    return res;
}

const int K = 470;
const int N = 1e6;

vector<int> s[N / K + 10];
int maxInverse[N / K + 10];

int calcMaxInv2(vector<int>& a, int l, int r) {
    int res = 0, maxVal = 0;
    if (l % K != 0) {
        res = calcMaxInv(a, l, min(r, l - l % K + K - 1));
        maxVal = *max_element(a.begin() + l, a.begin() + l - l % K + K - 1 + 1);
        l = l - l % K + K;
    }
    while (l + K - 1 <= r) {
        res = max(res, maxInverse[l / K]);
        auto it = lower_bound(s[l / K].begin(), s[l / K].end(), maxVal);
        if (it != s[l / K].begin()) {
            --it;
            res = max(res, *it + maxVal);
        }
        maxVal = max(maxVal, *s[l / K].rbegin());
        l += K;
    }
    if (l <= r) {
        for (int i = l; i <= r; ++i) {
            if (a[i] < maxVal) {
                res = max(res, a[i] + maxVal);
            }
        }
        res = max(res, calcMaxInv(a, l, r));
    }
    return res;
}

const int INF = 2e9;

struct segtree {
    int n;
    struct node {
        int min, max;
        bool isSorted;

        friend node combine(node a, node b) {
            if (!a.isSorted || !b.isSorted) {
                return {std::min(a.min, b.min), std::max(a.max, b.max), false};
            }
            if (a.max <= b.min) {
                return {std::min(a.min, b.min), std::max(a.max, b.max), true};
            }
            return {std::min(a.min, b.min), std::max(a.max, b.max), false};
        }
    };
    vector<node> tree;

    void build(vector<int>& a) {
        n = 1;
        while (n < a.size()) {
            n *= 2;
        }
        tree.assign(n * 2, {INF, -INF, true});
        for (int i = 0; i < a.size(); ++i) {
            tree[n - 1 + i] = {a[i], a[i], true};
        }
        for (int i = n - 2; i >= 0; --i) {
            tree[i] = combine(tree[2 * i + 1], tree[2 * i + 2]);
        }
    }

    node get(int l, int r, int x, int lx, int rx) {
        if (rx < l || r < lx) {
            return {INF, -INF, true};
        }
        if (l <= lx && rx <= r) {
            return tree[x];
        }
        node a = get(l, r, x * 2 + 1, lx, (lx + rx) / 2);
        node b = get(l, r, x * 2 + 2, (lx + rx) / 2 + 1, rx);
        return combine(a, b);
    }

    node get(int l, int r) {
        return get(l, r, 0, 0, n - 1);
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto& i : a) {
        cin >> i;
    }
    for (int i = 0; i < n; ++i) {
        s[i / K].push_back(a[i]);
    }
    for (auto& i : s) {
        sort(i.begin(), i.end());
    }
    for (int i = 0; (i + 1) * K - 1 < n; ++i) {
        maxInverse[i] = calcMaxInv(a, i * K, (i + 1) * K - 1);
    }
    int minVal = *min_element(a.begin(), a.end());
    segtree st;
    st.build(a);
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        --l, --r;
        if (k < minVal) {
            cout << st.get(l, r).isSorted << '\n';
//            cout << is_sorted(a.begin() + l, a.begin() + r + 1) << '\n';
        } else {
            cout << (calcMaxInv2(a, l, r) <= k) << '\n';
        }
    }
    return 0;
}

Compilation message

sortbooks.cpp: In member function 'void segtree::build(std::vector<int>&)':
sortbooks.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         while (n < a.size()) {
      |                ~~^~~~~~~~~~
sortbooks.cpp:76:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int i = 0; i < a.size(); ++i) {
      |                         ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 396 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 396 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 4 ms 588 KB Output is correct
13 Correct 5 ms 588 KB Output is correct
14 Correct 9 ms 624 KB Output is correct
15 Correct 8 ms 588 KB Output is correct
16 Correct 6 ms 588 KB Output is correct
17 Correct 6 ms 460 KB Output is correct
18 Correct 6 ms 588 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1192 ms 35220 KB Output is correct
2 Correct 1154 ms 35180 KB Output is correct
3 Correct 1160 ms 35176 KB Output is correct
4 Correct 1195 ms 35228 KB Output is correct
5 Correct 1155 ms 38632 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 4412 KB Output is correct
2 Correct 488 ms 4436 KB Output is correct
3 Correct 236 ms 4464 KB Output is correct
4 Correct 192 ms 4460 KB Output is correct
5 Correct 182 ms 4420 KB Output is correct
6 Correct 353 ms 4528 KB Output is correct
7 Correct 346 ms 4424 KB Output is correct
8 Correct 297 ms 4572 KB Output is correct
9 Correct 53 ms 464 KB Output is correct
10 Correct 282 ms 4400 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 396 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 4 ms 588 KB Output is correct
13 Correct 5 ms 588 KB Output is correct
14 Correct 9 ms 624 KB Output is correct
15 Correct 8 ms 588 KB Output is correct
16 Correct 6 ms 588 KB Output is correct
17 Correct 6 ms 460 KB Output is correct
18 Correct 6 ms 588 KB Output is correct
19 Correct 613 ms 8548 KB Output is correct
20 Correct 604 ms 8540 KB Output is correct
21 Correct 1379 ms 8580 KB Output is correct
22 Correct 1384 ms 8644 KB Output is correct
23 Correct 1382 ms 8536 KB Output is correct
24 Correct 1166 ms 8656 KB Output is correct
25 Correct 1075 ms 8564 KB Output is correct
26 Correct 905 ms 8620 KB Output is correct
27 Correct 886 ms 8556 KB Output is correct
28 Correct 802 ms 8568 KB Output is correct
29 Correct 514 ms 8632 KB Output is correct
30 Correct 473 ms 8520 KB Output is correct
31 Correct 536 ms 8596 KB Output is correct
32 Correct 514 ms 8564 KB Output is correct
33 Correct 564 ms 8516 KB Output is correct
34 Correct 1147 ms 8752 KB Output is correct
35 Correct 1169 ms 8512 KB Output is correct
36 Correct 1112 ms 8600 KB Output is correct
37 Correct 1151 ms 8556 KB Output is correct
38 Correct 1344 ms 8664 KB Output is correct
39 Correct 911 ms 8656 KB Output is correct
40 Correct 657 ms 4984 KB Output is correct
41 Correct 934 ms 8656 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 1 ms 396 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 4 ms 332 KB Output is correct
12 Correct 4 ms 588 KB Output is correct
13 Correct 5 ms 588 KB Output is correct
14 Correct 9 ms 624 KB Output is correct
15 Correct 8 ms 588 KB Output is correct
16 Correct 6 ms 588 KB Output is correct
17 Correct 6 ms 460 KB Output is correct
18 Correct 6 ms 588 KB Output is correct
19 Correct 1192 ms 35220 KB Output is correct
20 Correct 1154 ms 35180 KB Output is correct
21 Correct 1160 ms 35176 KB Output is correct
22 Correct 1195 ms 35228 KB Output is correct
23 Correct 1155 ms 38632 KB Output is correct
24 Correct 241 ms 4412 KB Output is correct
25 Correct 488 ms 4436 KB Output is correct
26 Correct 236 ms 4464 KB Output is correct
27 Correct 192 ms 4460 KB Output is correct
28 Correct 182 ms 4420 KB Output is correct
29 Correct 353 ms 4528 KB Output is correct
30 Correct 346 ms 4424 KB Output is correct
31 Correct 297 ms 4572 KB Output is correct
32 Correct 53 ms 464 KB Output is correct
33 Correct 282 ms 4400 KB Output is correct
34 Correct 613 ms 8548 KB Output is correct
35 Correct 604 ms 8540 KB Output is correct
36 Correct 1379 ms 8580 KB Output is correct
37 Correct 1384 ms 8644 KB Output is correct
38 Correct 1382 ms 8536 KB Output is correct
39 Correct 1166 ms 8656 KB Output is correct
40 Correct 1075 ms 8564 KB Output is correct
41 Correct 905 ms 8620 KB Output is correct
42 Correct 886 ms 8556 KB Output is correct
43 Correct 802 ms 8568 KB Output is correct
44 Correct 514 ms 8632 KB Output is correct
45 Correct 473 ms 8520 KB Output is correct
46 Correct 536 ms 8596 KB Output is correct
47 Correct 514 ms 8564 KB Output is correct
48 Correct 564 ms 8516 KB Output is correct
49 Correct 1147 ms 8752 KB Output is correct
50 Correct 1169 ms 8512 KB Output is correct
51 Correct 1112 ms 8600 KB Output is correct
52 Correct 1151 ms 8556 KB Output is correct
53 Correct 1344 ms 8664 KB Output is correct
54 Correct 911 ms 8656 KB Output is correct
55 Correct 657 ms 4984 KB Output is correct
56 Correct 934 ms 8656 KB Output is correct
57 Execution timed out 3035 ms 37500 KB Time limit exceeded
58 Halted 0 ms 0 KB -