oj.uz

Submission #956460

# Submission time Handle Problem Language Result Execution time Memory
956460 2024-04-02T01:56:58 Z Darren0724 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
17 / 100
 81 ms 10976 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=10005;
const int INF=1e9;
vector<int> t;
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]);
    }
    void ask(int id,int a,int b,int l,int r){
        if(a<=l&&b>=r)return t.push_back(id);
        int m=(l+r)>>1;
        if(a<m)ask(id<<1,a,b,l,m);
        if(b>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;
        t.clear();
        st.ask(1,l-1,r,0,n);
        int m=t.size();
        int mx=0;
        int ans=0;
        for(int j=0;j<m;j++){
            int f=t[j];
            auto &c=st.tr[f].v;
            ans=max(ans,st.tr[f].val);
            if(mx>c[0]){
                int t=lower_bound(all(c),mx)-c.begin()-1;
                ans=max(ans,mx+c[t]);
            }
            mx=max(mx,c.back());
        }
        cout<<(ans<=c)<<endl;
    }
    
    return 0;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1624 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1624 KB Output is correct
11 Correct 4 ms 1880 KB Output is correct
12 Correct 5 ms 2396 KB Output is correct
13 Correct 5 ms 2396 KB Output is correct
14 Correct 6 ms 2396 KB Output is correct
15 Correct 7 ms 2396 KB Output is correct
16 Correct 5 ms 2396 KB Output is correct
17 Correct 4 ms 2140 KB Output is correct
18 Correct 5 ms 2396 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1624 KB Output is correct
11 Correct 4 ms 1880 KB Output is correct
12 Correct 5 ms 2396 KB Output is correct
13 Correct 5 ms 2396 KB Output is correct
14 Correct 6 ms 2396 KB Output is correct
15 Correct 7 ms 2396 KB Output is correct
16 Correct 5 ms 2396 KB Output is correct
17 Correct 4 ms 2140 KB Output is correct
18 Correct 5 ms 2396 KB Output is correct
19 Runtime error 18 ms 4700 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1624 KB Output is correct
11 Correct 4 ms 1880 KB Output is correct
12 Correct 5 ms 2396 KB Output is correct
13 Correct 5 ms 2396 KB Output is correct
14 Correct 6 ms 2396 KB Output is correct
15 Correct 7 ms 2396 KB Output is correct
16 Correct 5 ms 2396 KB Output is correct
17 Correct 4 ms 2140 KB Output is correct
18 Correct 5 ms 2396 KB Output is correct
19 Runtime error 81 ms 10976 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -