제출 #1035346

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1035346		alexander707070	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	17 / 100	3076 ms	100660 KiB

sortbooks

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23