oj.uz

Submission #1111627

# Submission time Handle Problem Language Result Execution time Memory
1111627 2024-11-12T12:02:38 Z Pekiban Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 2101 ms 262144 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;
vector<int> st[4*N];
int mx[4*N], n;
void build(vector<int> &a, int i = 1, int l2 = 1, int r2 = n) {
    if (l2 == r2) {
        st[i]= {a[l2]};
        mx[i] = 0;
        return;
    }
    int m2 = (l2 + r2)/2;
    build(a, 2*i, l2, m2);
    build(a, 2*i+1, m2+1, r2);
    st[i].resize(r2 - l2 + 1);
    merge(st[2*i].begin(), st[2*i].end(), st[2*i+1].begin(), st[2*i+1].end(), st[i].begin());
    int id = upper_bound(st[2*i+1].begin(), st[2*i+1].end(), st[2*i].back()) - st[2*i+1].begin();
    if (!id)    mx[i] = max(mx[2*i], mx[2*i+1]);
    else {
        mx[i] = max({mx[2*i], mx[2*i+1], st[2*i].back() + st[2*i+1][id-1]});
    }
}
int M = 0, MS = 0;
void qry(int l, int r, int i = 1, int l2 = 1, int r2 = n) {
    if (l <= l2 && r2 <= r) {
        int id = upper_bound(st[i].begin(), st[i].end(), M) - st[i].begin();
        MS = max(MS, mx[i]);
        if (id) MS = max({MS, M + st[i][id-1]});
        M = max(M, st[i].back());
        return;
    }
    int m2 = (l2 + r2)/2;
    if (l <= m2)    qry(l, r, 2*i, l2, m2);
    if (m2 +1 <= r) qry(l, r, 2*i+1, m2+1, r2);   
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m;
    cin >> n >> m;
    vector<int> a(n+1);
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(a);
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        qry(l, r);
        cout << (MS <= k) << '\n'; 
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 95312 KB Output is correct
2 Correct 18 ms 95500 KB Output is correct
3 Incorrect 17 ms 95312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 95312 KB Output is correct
2 Correct 18 ms 95500 KB Output is correct
3 Incorrect 17 ms 95312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2101 ms 262144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 111624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 95312 KB Output is correct
2 Correct 18 ms 95500 KB Output is correct
3 Incorrect 17 ms 95312 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 95312 KB Output is correct
2 Correct 18 ms 95500 KB Output is correct
3 Incorrect 17 ms 95312 KB Output isn't correct
4 Halted 0 ms 0 KB -