oj.uz

Submission #932106

# Submission time Handle Problem Language Result Execution time Memory
932106 2024-02-23T02:37:42 Z thangdz2k7 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 984 ms 105756 KB 
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

const int N = 1e6 + 5;

int n, m;
int a[N], u[N], v[N], k[N];
vector <int> ask[N];
int ans[N];

int Max[4 * N];

void upd(int s, int l, int r, int u, int v, int val){
    if (u <= l && r <= v){
        Max[s] = max(Max[s], val);
        return;
    }

    int mid = l + r >> 1;
    if (mid >= u) upd(2 * s, l, mid, u, v, val);
    if (mid + 1 <= v) upd(2 * s + 1, mid + 1, r, u, v, val);
}

int get(int s, int l, int r, int u){
    if (l == r) return Max[s];
    int mid = l + r >> 1;
    if (mid >= u) return max(Max[s], get(2 * s, l, mid, u));
    return max(Max[s], get(2 * s + 1, mid + 1, r, u));
}

void solve(){
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> a[i];

    for (int i = 1; i <= m; ++ i){
        cin >> u[i] >> v[i] >> k[i];
        ask[v[i]].pb(i);
    }

    stack <int> st;
    for (int i = 1; i <= n; ++ i){
        while (!st.empty() && a[st.top()] < a[i]) st.pop();
        if (!st.empty()) upd(1, 1, n, 1, st.top(), a[i] + a[st.top()]);
        st.push(i);

        for (int z : ask[i]) if (get(1, 1, n, u[z]) <= k[z]) ans[z] = 1;
    }

    for (int i = 1; i <= m; ++ i) cout << ans[i] << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();

    return 0;
}

Compilation message

sortbooks.cpp: In function 'void upd(int, int, int, int, int, int)':
sortbooks.cpp:21:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int mid = l + r >> 1;
      |               ~~^~~
sortbooks.cpp: In function 'int get(int, int, int, int)':
sortbooks.cpp:28:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33112 KB Output is correct
2 Correct 6 ms 33116 KB Output is correct
3 Correct 7 ms 33112 KB Output is correct
4 Correct 9 ms 33112 KB Output is correct
5 Correct 7 ms 33116 KB Output is correct
6 Correct 7 ms 33116 KB Output is correct
7 Correct 7 ms 33116 KB Output is correct
8 Correct 7 ms 33116 KB Output is correct
9 Correct 8 ms 33284 KB Output is correct
10 Incorrect 7 ms 33116 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33112 KB Output is correct
2 Correct 6 ms 33116 KB Output is correct
3 Correct 7 ms 33112 KB Output is correct
4 Correct 9 ms 33112 KB Output is correct
5 Correct 7 ms 33116 KB Output is correct
6 Correct 7 ms 33116 KB Output is correct
7 Correct 7 ms 33116 KB Output is correct
8 Correct 7 ms 33116 KB Output is correct
9 Correct 8 ms 33284 KB Output is correct
10 Incorrect 7 ms 33116 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 922 ms 72720 KB Output is correct
2 Correct 984 ms 105756 KB Output is correct
3 Correct 950 ms 103572 KB Output is correct
4 Correct 971 ms 103552 KB Output is correct
5 Incorrect 808 ms 105316 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33112 KB Output is correct
2 Correct 6 ms 33116 KB Output is correct
3 Correct 7 ms 33112 KB Output is correct
4 Correct 9 ms 33112 KB Output is correct
5 Correct 7 ms 33116 KB Output is correct
6 Correct 7 ms 33116 KB Output is correct
7 Correct 7 ms 33116 KB Output is correct
8 Correct 7 ms 33116 KB Output is correct
9 Correct 8 ms 33284 KB Output is correct
10 Incorrect 7 ms 33116 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 33112 KB Output is correct
2 Correct 6 ms 33116 KB Output is correct
3 Correct 7 ms 33112 KB Output is correct
4 Correct 9 ms 33112 KB Output is correct
5 Correct 7 ms 33116 KB Output is correct
6 Correct 7 ms 33116 KB Output is correct
7 Correct 7 ms 33116 KB Output is correct
8 Correct 7 ms 33116 KB Output is correct
9 Correct 8 ms 33284 KB Output is correct
10 Incorrect 7 ms 33116 KB Output isn't correct
11 Halted 0 ms 0 KB -