oj.uz

Submission #956454

# Submission time Handle Problem Language Result Execution time Memory
956454 2024-04-02T01:30:28 Z Darren0724 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 3000 ms 262144 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=1000005;
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 77 ms 125524 KB Output is correct
2 Correct 79 ms 125620 KB Output is correct
3 Correct 85 ms 125740 KB Output is correct
4 Correct 81 ms 125668 KB Output is correct
5 Correct 79 ms 125476 KB Output is correct
6 Correct 80 ms 125520 KB Output is correct
7 Correct 84 ms 125568 KB Output is correct
8 Correct 85 ms 125524 KB Output is correct
9 Correct 79 ms 125620 KB Output is correct
10 Correct 89 ms 125704 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 125524 KB Output is correct
2 Correct 79 ms 125620 KB Output is correct
3 Correct 85 ms 125740 KB Output is correct
4 Correct 81 ms 125668 KB Output is correct
5 Correct 79 ms 125476 KB Output is correct
6 Correct 80 ms 125520 KB Output is correct
7 Correct 84 ms 125568 KB Output is correct
8 Correct 85 ms 125524 KB Output is correct
9 Correct 79 ms 125620 KB Output is correct
10 Correct 89 ms 125704 KB Output is correct
11 Correct 108 ms 126124 KB Output is correct
12 Correct 158 ms 126208 KB Output is correct
13 Correct 172 ms 126288 KB Output is correct
14 Correct 227 ms 126288 KB Output is correct
15 Correct 218 ms 126180 KB Output is correct
16 Correct 147 ms 126292 KB Output is correct
17 Correct 102 ms 126124 KB Output is correct
18 Correct 131 ms 126288 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 125524 KB Output is correct
2 Correct 79 ms 125620 KB Output is correct
3 Correct 85 ms 125740 KB Output is correct
4 Correct 81 ms 125668 KB Output is correct
5 Correct 79 ms 125476 KB Output is correct
6 Correct 80 ms 125520 KB Output is correct
7 Correct 84 ms 125568 KB Output is correct
8 Correct 85 ms 125524 KB Output is correct
9 Correct 79 ms 125620 KB Output is correct
10 Correct 89 ms 125704 KB Output is correct
11 Correct 108 ms 126124 KB Output is correct
12 Correct 158 ms 126208 KB Output is correct
13 Correct 172 ms 126288 KB Output is correct
14 Correct 227 ms 126288 KB Output is correct
15 Correct 218 ms 126180 KB Output is correct
16 Correct 147 ms 126292 KB Output is correct
17 Correct 102 ms 126124 KB Output is correct
18 Correct 131 ms 126288 KB Output is correct
19 Execution timed out 3108 ms 156680 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 125524 KB Output is correct
2 Correct 79 ms 125620 KB Output is correct
3 Correct 85 ms 125740 KB Output is correct
4 Correct 81 ms 125668 KB Output is correct
5 Correct 79 ms 125476 KB Output is correct
6 Correct 80 ms 125520 KB Output is correct
7 Correct 84 ms 125568 KB Output is correct
8 Correct 85 ms 125524 KB Output is correct
9 Correct 79 ms 125620 KB Output is correct
10 Correct 89 ms 125704 KB Output is correct
11 Correct 108 ms 126124 KB Output is correct
12 Correct 158 ms 126208 KB Output is correct
13 Correct 172 ms 126288 KB Output is correct
14 Correct 227 ms 126288 KB Output is correct
15 Correct 218 ms 126180 KB Output is correct
16 Correct 147 ms 126292 KB Output is correct
17 Correct 102 ms 126124 KB Output is correct
18 Correct 131 ms 126288 KB Output is correct
19 Runtime error 497 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -