oj.uz

Submission #956455

# Submission time Handle Problem Language Result Execution time Memory
956455 2024-04-02T01:31:20 Z Darren0724 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 118960 KB 
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=300005;
const int INF=1e9;
struct segtree{
    struct seg{
        vector<int> v;
        int val=0;
    }tr[N<<2];
    seg merge(seg a,seg b){
        seg ans;
        ans.val=max(a.val,b.val);
        auto &c=a.v,&d=b.v;
        int ptr1=0,ptr2=0;
        while(ptr1<c.size()&&ptr2<d.size()){
            if(c[ptr1]<=d[ptr2]){
                if(ptr2>0)ans.val=max(ans.val,c[ptr1]+d[ptr2-1]);
                ans.v.push_back(c[ptr1++]);
            }
            else{
                ans.v.push_back(d[ptr2++]);
            }
        }
        while(ptr1<c.size()){
            if(ptr2>0)ans.val=max(ans.val,c[ptr1]+d[ptr2-1]);
            ans.v.push_back(c[ptr1++]);
        }
        while(ptr2<d.size()){
            ans.v.push_back(d[ptr2++]);
        }
        return ans;
    }
    void build(vector<int> &a,int id,int l,int r){
        if(r-l==1){
            tr[id].v.push_back(a[l]);
            return;        
        }
        int m=(l+r)>>1;
        build(a,id<<1,l,m);
        build(a,id<<1|1,m,r);
        tr[id]=merge(tr[id<<1],tr[id<<1|1]);
    }
    seg ask(int id,int a,int b,int l,int r){
        if(a<=l&&b>=r)return tr[id];
        int m=(l+r)>>1;
        if(b<=m)return ask(id<<1,a,b,l,m);
        if(a>=m)return ask(id<<1|1,a,b,m,r);
        return merge(ask(id<<1,a,b,l,m),ask(id<<1|1,a,b,m,r));
    }
};
int32_t main() {
    LCBorz;
    int n,q;cin>>n>>q;
    vector<int> v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    segtree st;
    st.build(v,1,0,n);
    for(int i=0;i<q;i++){
        int l,r,c;cin>>l>>r>>c;
        segtree::seg t=st.ask(1,l-1,r,0,n);
        cout<<(t.val<=c)<<endl;
    }
    
    return 0;
}

Compilation message

sortbooks.cpp: In member function 'segtree::seg segtree::merge(segtree::seg, segtree::seg)':
sortbooks.cpp:18:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         while(ptr1<c.size()&&ptr2<d.size()){
      |               ~~~~^~~~~~~~~
sortbooks.cpp:18:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         while(ptr1<c.size()&&ptr2<d.size()){
      |                              ~~~~^~~~~~~~~
sortbooks.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         while(ptr1<c.size()){
      |               ~~~~^~~~~~~~~
sortbooks.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |         while(ptr2<d.size()){
      |               ~~~~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37976 KB Output is correct
2 Correct 24 ms 37980 KB Output is correct
3 Correct 25 ms 37980 KB Output is correct
4 Correct 27 ms 37980 KB Output is correct
5 Correct 26 ms 38264 KB Output is correct
6 Correct 27 ms 37976 KB Output is correct
7 Correct 27 ms 37980 KB Output is correct
8 Correct 26 ms 37980 KB Output is correct
9 Correct 27 ms 37980 KB Output is correct
10 Correct 26 ms 37976 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37976 KB Output is correct
2 Correct 24 ms 37980 KB Output is correct
3 Correct 25 ms 37980 KB Output is correct
4 Correct 27 ms 37980 KB Output is correct
5 Correct 26 ms 38264 KB Output is correct
6 Correct 27 ms 37976 KB Output is correct
7 Correct 27 ms 37980 KB Output is correct
8 Correct 26 ms 37980 KB Output is correct
9 Correct 27 ms 37980 KB Output is correct
10 Correct 26 ms 37976 KB Output is correct
11 Correct 56 ms 37980 KB Output is correct
12 Correct 98 ms 38732 KB Output is correct
13 Correct 113 ms 38740 KB Output is correct
14 Correct 161 ms 38736 KB Output is correct
15 Correct 163 ms 38752 KB Output is correct
16 Correct 105 ms 38748 KB Output is correct
17 Correct 47 ms 38488 KB Output is correct
18 Correct 82 ms 39120 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3057 ms 53140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37976 KB Output is correct
2 Correct 24 ms 37980 KB Output is correct
3 Correct 25 ms 37980 KB Output is correct
4 Correct 27 ms 37980 KB Output is correct
5 Correct 26 ms 38264 KB Output is correct
6 Correct 27 ms 37976 KB Output is correct
7 Correct 27 ms 37980 KB Output is correct
8 Correct 26 ms 37980 KB Output is correct
9 Correct 27 ms 37980 KB Output is correct
10 Correct 26 ms 37976 KB Output is correct
11 Correct 56 ms 37980 KB Output is correct
12 Correct 98 ms 38732 KB Output is correct
13 Correct 113 ms 38740 KB Output is correct
14 Correct 161 ms 38736 KB Output is correct
15 Correct 163 ms 38752 KB Output is correct
16 Correct 105 ms 38748 KB Output is correct
17 Correct 47 ms 38488 KB Output is correct
18 Correct 82 ms 39120 KB Output is correct
19 Execution timed out 3063 ms 69060 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37976 KB Output is correct
2 Correct 24 ms 37980 KB Output is correct
3 Correct 25 ms 37980 KB Output is correct
4 Correct 27 ms 37980 KB Output is correct
5 Correct 26 ms 38264 KB Output is correct
6 Correct 27 ms 37976 KB Output is correct
7 Correct 27 ms 37980 KB Output is correct
8 Correct 26 ms 37980 KB Output is correct
9 Correct 27 ms 37980 KB Output is correct
10 Correct 26 ms 37976 KB Output is correct
11 Correct 56 ms 37980 KB Output is correct
12 Correct 98 ms 38732 KB Output is correct
13 Correct 113 ms 38740 KB Output is correct
14 Correct 161 ms 38736 KB Output is correct
15 Correct 163 ms 38752 KB Output is correct
16 Correct 105 ms 38748 KB Output is correct
17 Correct 47 ms 38488 KB Output is correct
18 Correct 82 ms 39120 KB Output is correct
19 Runtime error 191 ms 118960 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -