제출 #1175870

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1175870		Newtonabc	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	3096 ms	22228 KiB

sortbooks

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int N=1<<21;
int s[N],w[N],ans[N];
vector<pair<pii,pii>> qr;
bool cp(const pair<pii,pii>&a,const pair<pii,pii>&b){
    return a.first.second<b.first.second;
}
void update(int l,int r,int idx,int a,int b){
    if(a<l || a>r) return;
    if(l==r){
        s[idx]=max(s[idx],b);
        return;
    }
    int m=(l+r)/2;
    update(l,m,idx*2+1,a,b);
    update(m+1,r,idx*2+1,a,b);
    s[idx]=max(s[idx*2],s[idx*2+1]);
}
int query(int l,int r,int idx,int a,int b){
    if(b<l || a>r) return INT_MIN;
    if(a<=l && b>=r) return s[idx];
    int m=(l+r)/2;
    return max(query(l,m,idx*2,a,b),query(m+1,r,idx*2+1,a,b));
}
int main(){
    int n,m;
    cin>>n >>m;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=0;i<m;i++){
        int a,b,c,d;
        cin>>a >>b >>c;
        qr.push_back({{a,b},{c,i}});
    }
    stack<pii> st;
    //sort by r
    sort(qr.begin(),qr.end(),cp);
    int prev=0;
    for(int i=0;i<m;i++){
        auto [pa,pb]=qr[i];
        auto [l,r]=pa;
        auto [k,idx]=pb;
        for(int j=prev+1;j<=r;j++){
            //update w[j]+(top of stack) to top of stack index
            if(st.empty()){
                st.push({w[j],j});
                continue;
            }
            while(!st.empty() && st.top().first<=w[j]) st.pop();
            if(!st.empty()) update(1,n,1,st.top().second,st.top().first+w[j]);
            st.push({w[j],j});
        }
        ans[idx]=query(1,n,1,l,r)<=k;
    }
    for(int i=0;i<m;i++) cout<<ans[i] <<"\n";
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23