oj.uz

Submission #1115083

# Submission time Handle Problem Language Result Execution time Memory
1115083 2024-11-20T03:09:39 Z Zero_OP Fire (JOI20_ho_t5) C++14
7 / 100
 121 ms 11592 KB 
#include <bits/stdc++.h>

using namespace std;

struct segment_tree{
    vector<int> st;
    segment_tree(int n) : st(n << 2) {}

    void build(int id, int l, int r, const vector<int>& S){
        if(l == r) st[id] = S[l];
        else{
            int mid = l + r >> 1;
            build(id << 1, l, mid, S);
            build(id << 1 | 1, mid + 1, r, S);
            st[id] = max(st[id << 1], st[id << 1 | 1]);
        }
    }

    int query(int id, int l, int r, int u, int v){
        if(v < l || u > r) return 0;
        if(u <= l && r <= v) return st[id];
        int mid = l + r >> 1;
        return max(query(id << 1, l, mid, u, v), query(id << 1 | 1, mid + 1, r, u, v));
    }
};

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

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N, Q;
    cin >> N >> Q;
    vector<int> S(N + 1);
    for(int i = 1; i <= N; ++i) cin >> S[i];

    segment_tree st(N);
    st.build(1, 1, N, S);

    for(int i = 0; i < Q; ++i){
        int t, l, r;
        cin >> t >> l >> r;
        cout << st.query(1, 1, N, l - t, l) << '\n';
    }



    return 0;
}

/*

*/

Compilation message

ho_t5.cpp: In member function 'void segment_tree::build(int, int, int, const std::vector<int>&)':
ho_t5.cpp:12:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   12 |             int mid = l + r >> 1;
      |                       ~~^~~
ho_t5.cpp: In member function 'int segment_tree::query(int, int, int, int, int)':
ho_t5.cpp:22:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 102 ms 10792 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 114 ms 9556 KB Output is correct
3 Correct 110 ms 10696 KB Output is correct
4 Correct 109 ms 11080 KB Output is correct
5 Correct 104 ms 10128 KB Output is correct
6 Correct 102 ms 11592 KB Output is correct
7 Correct 100 ms 11532 KB Output is correct
8 Correct 121 ms 9180 KB Output is correct
9 Correct 116 ms 11336 KB Output is correct
10 Correct 114 ms 9032 KB Output is correct
11 Correct 108 ms 11592 KB Output is correct
12 Correct 107 ms 11592 KB Output is correct
13 Correct 111 ms 9800 KB Output is correct
14 Correct 120 ms 10056 KB Output is correct
15 Correct 107 ms 10892 KB Output is correct
16 Correct 109 ms 10568 KB Output is correct

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -