oj.uz

Submission #956456

# Submission time Handle Problem Language Result Execution time Memory
956456 2024-04-02T01:35:00 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);
    if(n>5000){
        while(1){}
    }
    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 81 ms 125420 KB Output is correct
2 Correct 82 ms 125548 KB Output is correct
3 Correct 80 ms 125588 KB Output is correct
4 Correct 79 ms 125524 KB Output is correct
5 Correct 79 ms 125520 KB Output is correct
6 Correct 80 ms 125520 KB Output is correct
7 Correct 87 ms 125520 KB Output is correct
8 Correct 89 ms 125492 KB Output is correct
9 Correct 80 ms 125528 KB Output is correct
10 Correct 81 ms 125672 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 125420 KB Output is correct
2 Correct 82 ms 125548 KB Output is correct
3 Correct 80 ms 125588 KB Output is correct
4 Correct 79 ms 125524 KB Output is correct
5 Correct 79 ms 125520 KB Output is correct
6 Correct 80 ms 125520 KB Output is correct
7 Correct 87 ms 125520 KB Output is correct
8 Correct 89 ms 125492 KB Output is correct
9 Correct 80 ms 125528 KB Output is correct
10 Correct 81 ms 125672 KB Output is correct
11 Correct 111 ms 125944 KB Output is correct
12 Correct 154 ms 126288 KB Output is correct
13 Correct 162 ms 126408 KB Output is correct
14 Correct 227 ms 126424 KB Output is correct
15 Correct 218 ms 126356 KB Output is correct
16 Correct 164 ms 126288 KB Output is correct
17 Correct 102 ms 126032 KB Output is correct
18 Correct 134 ms 126196 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 477 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 3008 ms 139812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 125420 KB Output is correct
2 Correct 82 ms 125548 KB Output is correct
3 Correct 80 ms 125588 KB Output is correct
4 Correct 79 ms 125524 KB Output is correct
5 Correct 79 ms 125520 KB Output is correct
6 Correct 80 ms 125520 KB Output is correct
7 Correct 87 ms 125520 KB Output is correct
8 Correct 89 ms 125492 KB Output is correct
9 Correct 80 ms 125528 KB Output is correct
10 Correct 81 ms 125672 KB Output is correct
11 Correct 111 ms 125944 KB Output is correct
12 Correct 154 ms 126288 KB Output is correct
13 Correct 162 ms 126408 KB Output is correct
14 Correct 227 ms 126424 KB Output is correct
15 Correct 218 ms 126356 KB Output is correct
16 Correct 164 ms 126288 KB Output is correct
17 Correct 102 ms 126032 KB Output is correct
18 Correct 134 ms 126196 KB Output is correct
19 Execution timed out 3019 ms 154856 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 125420 KB Output is correct
2 Correct 82 ms 125548 KB Output is correct
3 Correct 80 ms 125588 KB Output is correct
4 Correct 79 ms 125524 KB Output is correct
5 Correct 79 ms 125520 KB Output is correct
6 Correct 80 ms 125520 KB Output is correct
7 Correct 87 ms 125520 KB Output is correct
8 Correct 89 ms 125492 KB Output is correct
9 Correct 80 ms 125528 KB Output is correct
10 Correct 81 ms 125672 KB Output is correct
11 Correct 111 ms 125944 KB Output is correct
12 Correct 154 ms 126288 KB Output is correct
13 Correct 162 ms 126408 KB Output is correct
14 Correct 227 ms 126424 KB Output is correct
15 Correct 218 ms 126356 KB Output is correct
16 Correct 164 ms 126288 KB Output is correct
17 Correct 102 ms 126032 KB Output is correct
18 Correct 134 ms 126196 KB Output is correct
19 Runtime error 477 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -