oj.uz

Submission #964078

# Submission time Handle Problem Language Result Execution time Memory
964078 2024-04-16T09:38:04 Z zxcigan Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
34 / 100
 89 ms 23228 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const int N = 1e5 + 1;
const int mod = 1e9 + 7;

template <typename T>
bool umx(T& a, T b) {
    return (a < b ? a = b, 1 : 0);
}
template <typename T>
bool umn(T& a, T b) {
    return (a > b ? a = b, 1 : 0);
}
int t[4 * N];
vector<array<int,3>> query[N];
void update (int v, int tl, int tr, int pos, int x) {
    if (tl == tr) {
        umx (t[v], x);
        return;
    }
    int tm = (tr + tl) >> 1;
    if (pos <= tm) update (v << 1, tl, tm, pos, x);
    else update (v << 1 | 1, tm + 1, tr, pos, x);
    t[v] = max (t[v << 1], t[v << 1 | 1]);
}
int get (int v, int tl, int tr, int l, int r) {
    if (l > r) return 0;
    if (l == tl && r == tr) return t[v];
    int tm = (tr + tl) >> 1;
    return max (get (v << 1, tl, tm, l, min (r, tm)), get (v << 1 | 1, tm + 1, tr, max (l, tm + 1), r));
}
void solve () {
    int n, q;
    cin >> n >> q;
    vector<int> w (n + 1);
    for (int i = 1; i <= n; ++i) cin >> w[i];
    for (int i = 1; i <= q; ++i) {
        int l, r, k;
        cin >> l >> r >> k;
        query[r].push_back ({l, k, i});
    }
    vector<int> ans (q + 1);
    vector<int> ve;
    for (int right = 1; right <= n; ++right) {
        while ((int)ve.size() && w[ve.back()] <= w[right]) {
            ve.pop_back();
        }
        if ((int)ve.size()) update (1, 1, n, ve.back(), w[right] + w[ve.back()]);
        ve.push_back(right);
        for (auto [l, k, i] : query[right]) {
            ans[i] = bool(get (1, 1, n, l, right) <= k);
        }
    }
    for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
    cout << endl;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    //    freopen ("input.txt", "r", stdin);
//    freopen ("output.txt", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    while (T--) solve();
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 2 ms 2904 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 3 ms 3084 KB Output is correct
14 Correct 5 ms 3160 KB Output is correct
15 Correct 4 ms 3164 KB Output is correct
16 Correct 3 ms 3084 KB Output is correct
17 Correct 3 ms 3160 KB Output is correct
18 Correct 3 ms 2908 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 23228 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 8776 KB Output is correct
2 Correct 76 ms 8448 KB Output is correct
3 Correct 59 ms 7564 KB Output is correct
4 Correct 57 ms 7760 KB Output is correct
5 Correct 57 ms 7764 KB Output is correct
6 Correct 51 ms 7472 KB Output is correct
7 Correct 50 ms 7252 KB Output is correct
8 Correct 51 ms 7432 KB Output is correct
9 Correct 27 ms 6152 KB Output is correct
10 Correct 50 ms 7348 KB Output is correct

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 2 ms 2904 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 3 ms 3084 KB Output is correct
14 Correct 5 ms 3160 KB Output is correct
15 Correct 4 ms 3164 KB Output is correct
16 Correct 3 ms 3084 KB Output is correct
17 Correct 3 ms 3160 KB Output is correct
18 Correct 3 ms 2908 KB Output is correct
19 Runtime error 19 ms 9084 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 3 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 1 ms 2652 KB Output is correct
11 Correct 2 ms 2904 KB Output is correct
12 Correct 3 ms 2908 KB Output is correct
13 Correct 3 ms 3084 KB Output is correct
14 Correct 5 ms 3160 KB Output is correct
15 Correct 4 ms 3164 KB Output is correct
16 Correct 3 ms 3084 KB Output is correct
17 Correct 3 ms 3160 KB Output is correct
18 Correct 3 ms 2908 KB Output is correct
19 Runtime error 89 ms 23228 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -