oj.uz

Submission #1047942

# Submission time Handle Problem Language Result Execution time Memory
1047942 2024-08-07T17:59:26 Z TAhmed33 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++
64 / 100
 600 ms 262144 KB 
    #include <bits/stdc++.h>
    #define int long long
    using namespace std; 
    int const mxN = 1e6+5;
    int n, pw; 
    vector<int> seg [4*mxN];
    int ans[4*mxN], a[4*mxN];
     
    void build ( int node, int l, int r) {
       if(l==r-1) { seg[node].push_back(a[l]); return; }
       int m = (l+r)/2;
       build(node*2+1, l, m) , build(node*2+2, m, r);
     
       seg[node] = seg[node*2+1];
       int maxi = seg[node].back();
     
       for(auto it:seg[node*2+2]) seg[node].push_back(it);
       sort(seg[node].begin(),seg[node].end());
       
       int ind = lower_bound(seg[node*2+2].begin(), seg[node*2+2].end(), maxi) - seg[node*2+2].begin(); ind--;
       if(ind<0) ans[node] = 0;
       else { ans[node] = seg[node*2+2][ind] + maxi; }
       ans[node] = max ({ans[node], ans[node*2+1], ans[node*2+2]});
    }
     
    int fin = 0, maxi = 0;
     
    void get ( int node, int l_n, int r_n, int l, int r) {
       if(l_n>=r || r_n<=l) return;
       if(l<=l_n && r>=r_n) {
          fin = max (fin, ans[node]);
          int ind = lower_bound(seg[node].begin(), seg[node].end(), maxi) - seg[node].begin(); ind--;
          if(ind>=0) {
             fin = max ( fin, maxi+seg[node][ind]);
          }
          maxi = max ( maxi, seg[node].back());
          return;
       }
       int m = (l_n+r_n) / 2;
       get(node*2+1, l_n, m, l, r), get(node*2+2, m ,r_n, l, r);
    }
     
    signed main() {
       ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
       
       cin>>n;       int q; cin>>q;

       for(int i=0; i<n; i++) cin>>a[i];
       pw = (1<<(__lg(n-1)+1));
       build(0,0,pw);
     
       while(q--) {
          int x,y; cin>>x>>y; int k; cin >> k;
          x--;
          fin = 0, maxi = 0;
          get(0,0,pw,x,y);
          cout<<(fin <= k)<<'\n';
       }
       return 0;}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 97328 KB Output is correct
2 Correct 14 ms 97280 KB Output is correct
3 Correct 13 ms 97356 KB Output is correct
4 Correct 16 ms 97120 KB Output is correct
5 Correct 15 ms 97360 KB Output is correct
6 Correct 14 ms 97280 KB Output is correct
7 Correct 14 ms 97344 KB Output is correct
8 Correct 15 ms 97372 KB Output is correct
9 Correct 14 ms 97372 KB Output is correct
10 Correct 14 ms 97372 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 97328 KB Output is correct
2 Correct 14 ms 97280 KB Output is correct
3 Correct 13 ms 97356 KB Output is correct
4 Correct 16 ms 97120 KB Output is correct
5 Correct 15 ms 97360 KB Output is correct
6 Correct 14 ms 97280 KB Output is correct
7 Correct 14 ms 97344 KB Output is correct
8 Correct 15 ms 97372 KB Output is correct
9 Correct 14 ms 97372 KB Output is correct
10 Correct 14 ms 97372 KB Output is correct
11 Correct 17 ms 97628 KB Output is correct
12 Correct 18 ms 98652 KB Output is correct
13 Correct 19 ms 98668 KB Output is correct
14 Correct 19 ms 98648 KB Output is correct
15 Correct 20 ms 98592 KB Output is correct
16 Correct 18 ms 98740 KB Output is correct
17 Correct 16 ms 98076 KB Output is correct
18 Correct 20 ms 98624 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 600 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 125484 KB Output is correct
2 Correct 133 ms 125636 KB Output is correct
3 Correct 134 ms 125704 KB Output is correct
4 Correct 126 ms 125684 KB Output is correct
5 Correct 126 ms 125812 KB Output is correct
6 Correct 115 ms 125628 KB Output is correct
7 Correct 95 ms 125488 KB Output is correct
8 Correct 119 ms 125420 KB Output is correct
9 Correct 37 ms 98660 KB Output is correct
10 Correct 125 ms 125564 KB Output is correct

Subtask #5
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 97328 KB Output is correct
2 Correct 14 ms 97280 KB Output is correct
3 Correct 13 ms 97356 KB Output is correct
4 Correct 16 ms 97120 KB Output is correct
5 Correct 15 ms 97360 KB Output is correct
6 Correct 14 ms 97280 KB Output is correct
7 Correct 14 ms 97344 KB Output is correct
8 Correct 15 ms 97372 KB Output is correct
9 Correct 14 ms 97372 KB Output is correct
10 Correct 14 ms 97372 KB Output is correct
11 Correct 17 ms 97628 KB Output is correct
12 Correct 18 ms 98652 KB Output is correct
13 Correct 19 ms 98668 KB Output is correct
14 Correct 19 ms 98648 KB Output is correct
15 Correct 20 ms 98592 KB Output is correct
16 Correct 18 ms 98740 KB Output is correct
17 Correct 16 ms 98076 KB Output is correct
18 Correct 20 ms 98624 KB Output is correct
19 Correct 370 ms 156500 KB Output is correct
20 Correct 379 ms 157124 KB Output is correct
21 Correct 297 ms 156900 KB Output is correct
22 Correct 321 ms 157008 KB Output is correct
23 Correct 335 ms 156816 KB Output is correct
24 Correct 226 ms 156768 KB Output is correct
25 Correct 232 ms 156868 KB Output is correct
26 Correct 264 ms 157120 KB Output is correct
27 Correct 266 ms 157124 KB Output is correct
28 Correct 283 ms 157124 KB Output is correct
29 Correct 291 ms 157176 KB Output is correct
30 Correct 286 ms 157124 KB Output is correct
31 Correct 306 ms 157124 KB Output is correct
32 Correct 290 ms 157216 KB Output is correct
33 Correct 317 ms 157036 KB Output is correct
34 Correct 205 ms 156832 KB Output is correct
35 Correct 204 ms 156608 KB Output is correct
36 Correct 246 ms 156600 KB Output is correct
37 Correct 217 ms 156592 KB Output is correct
38 Correct 214 ms 156732 KB Output is correct
39 Correct 253 ms 155584 KB Output is correct
40 Correct 143 ms 128452 KB Output is correct
41 Correct 222 ms 155196 KB Output is correct

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 97328 KB Output is correct
2 Correct 14 ms 97280 KB Output is correct
3 Correct 13 ms 97356 KB Output is correct
4 Correct 16 ms 97120 KB Output is correct
5 Correct 15 ms 97360 KB Output is correct
6 Correct 14 ms 97280 KB Output is correct
7 Correct 14 ms 97344 KB Output is correct
8 Correct 15 ms 97372 KB Output is correct
9 Correct 14 ms 97372 KB Output is correct
10 Correct 14 ms 97372 KB Output is correct
11 Correct 17 ms 97628 KB Output is correct
12 Correct 18 ms 98652 KB Output is correct
13 Correct 19 ms 98668 KB Output is correct
14 Correct 19 ms 98648 KB Output is correct
15 Correct 20 ms 98592 KB Output is correct
16 Correct 18 ms 98740 KB Output is correct
17 Correct 16 ms 98076 KB Output is correct
18 Correct 20 ms 98624 KB Output is correct
19 Runtime error 600 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -