oj.uz

Submission #1035346

# Submission time Handle Problem Language Result Execution time Memory
1035346 2024-07-26T09:41:04 Z alexander707070 Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++14
17 / 100
 3000 ms 100660 KB 
#include<bits/stdc++.h>
#define MAXN 1000007
using namespace std;

const int inf=1e9+7;

struct event{
    int r,k,id;
};

int n,w[MAXN],q,l,r,k[MAXN],ans[MAXN];
vector<event> qs[MAXN];

int tree[4*MAXN];

void build(int v,int l,int r){
    if(l==r){
        tree[v]=w[l];
    }else{
        int tt=(l+r)/2;
        build(2*v,l,tt);
        build(2*v+1,tt+1,r);

        tree[v]=max(tree[2*v],tree[2*v+1]);
    }
}

int getmax(int v,int l,int r,int ll,int rr){
    if(ll>rr)return 0;
    if(l==ll and r==rr)return tree[v];

    int tt=(l+r)/2;
    return max( getmax(2*v,l,tt,ll,min(tt,rr)) , getmax(2*v+1,tt+1,r,max(tt+1,ll),rr) );
}

vector< pair<int,int> > st;


int main(){

    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>w[i];
    }
    build(1,1,n);

    for(int i=1;i<=q;i++){
        cin>>l>>r>>k[i];
        qs[l].push_back({r,k[i],i});
    }

    st.push_back({n+1,0});
    w[n+1]=inf;

    for(int i=n;i>=1;i--){
        pair<int,int> curr={i,0};

        while(!st.empty() and w[i]>w[st.back().first]){
            curr.second=w[i]+w[st.back().first];
            st.pop_back();
        }

        st.push_back(curr);

        for(int f=0;f<qs[i].size();f++){
    
            for(int k=st.size()-1;k>=0;k--){
                if(st[k-1].first<=qs[i][f].r)ans[qs[i][f].id]=max(ans[qs[i][f].id],st[k].second);
                else{
                    if(st[k].first+1<=qs[i][f].r){
                        int s=getmax(1,1,n,st[k].first+1,qs[i][f].r);
                        ans[qs[i][f].id]=max(ans[qs[i][f].id],w[st[k].first]+s);
                    }

                    break;
                }
            }
        }
    }

    for(int i=1;i<=q;i++){
        if(ans[i]>k[i])cout<<"0\n";
        else cout<<"1\n";
    }

    return 0;
}

Compilation message

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int f=0;f<qs[i].size();f++){
      |                     ~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23852 KB Output is correct
4 Correct 10 ms 23728 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23916 KB Output is correct
7 Correct 10 ms 23972 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23852 KB Output is correct
4 Correct 10 ms 23728 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23916 KB Output is correct
7 Correct 10 ms 23972 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 13 ms 23900 KB Output is correct
12 Correct 13 ms 24088 KB Output is correct
13 Correct 14 ms 24056 KB Output is correct
14 Correct 16 ms 24128 KB Output is correct
15 Correct 14 ms 24156 KB Output is correct
16 Correct 27 ms 24252 KB Output is correct
17 Correct 25 ms 24152 KB Output is correct
18 Correct 20 ms 24156 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1314 ms 99320 KB Output is correct
2 Correct 1309 ms 100328 KB Output is correct
3 Correct 1357 ms 100280 KB Output is correct
4 Correct 1276 ms 100436 KB Output is correct
5 Execution timed out 3066 ms 100660 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 30544 KB Output is correct
2 Correct 112 ms 30192 KB Output is correct
3 Execution timed out 3068 ms 31188 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23852 KB Output is correct
4 Correct 10 ms 23728 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23916 KB Output is correct
7 Correct 10 ms 23972 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 13 ms 23900 KB Output is correct
12 Correct 13 ms 24088 KB Output is correct
13 Correct 14 ms 24056 KB Output is correct
14 Correct 16 ms 24128 KB Output is correct
15 Correct 14 ms 24156 KB Output is correct
16 Correct 27 ms 24252 KB Output is correct
17 Correct 25 ms 24152 KB Output is correct
18 Correct 20 ms 24156 KB Output is correct
19 Correct 257 ms 39764 KB Output is correct
20 Correct 262 ms 39760 KB Output is correct
21 Correct 230 ms 38996 KB Output is correct
22 Correct 241 ms 39140 KB Output is correct
23 Correct 227 ms 39200 KB Output is correct
24 Execution timed out 3076 ms 40392 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB Output is correct
2 Correct 10 ms 23900 KB Output is correct
3 Correct 10 ms 23852 KB Output is correct
4 Correct 10 ms 23728 KB Output is correct
5 Correct 10 ms 23900 KB Output is correct
6 Correct 10 ms 23916 KB Output is correct
7 Correct 10 ms 23972 KB Output is correct
8 Correct 10 ms 23900 KB Output is correct
9 Correct 10 ms 23900 KB Output is correct
10 Correct 11 ms 23900 KB Output is correct
11 Correct 13 ms 23900 KB Output is correct
12 Correct 13 ms 24088 KB Output is correct
13 Correct 14 ms 24056 KB Output is correct
14 Correct 16 ms 24128 KB Output is correct
15 Correct 14 ms 24156 KB Output is correct
16 Correct 27 ms 24252 KB Output is correct
17 Correct 25 ms 24152 KB Output is correct
18 Correct 20 ms 24156 KB Output is correct
19 Correct 1314 ms 99320 KB Output is correct
20 Correct 1309 ms 100328 KB Output is correct
21 Correct 1357 ms 100280 KB Output is correct
22 Correct 1276 ms 100436 KB Output is correct
23 Execution timed out 3066 ms 100660 KB Time limit exceeded
24 Halted 0 ms 0 KB -