Submission #802475

#	Time	Username	Problem	Language	Result	Execution time	Memory
802475		Ahmed57	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1604 ms	67364 KiB

sortbooks

#include<bits/stdc++.h>

using namespace std;
struct query{
    int id,l,r,mood;
};
bool comp(query a, query b){
    return a.l>b.l;
}
//BIT Fenwick tree
int n ;
long long bit[1000001]={0};
void add(int e,long long v){
    while(e<=n){
        bit[e] = max(bit[e],v);
        e+=e&-e;
    }
}
long long sum(int e){
    long long res = 0;
    while(e>=1){
        res=max(res,bit[e]);
        e -= e&-e;
    }
    return res;
}
//end BIT
int main(){
	int q;
	cin>>n>>q;
	int arr[n+1];
    for(int i = 1;i<=n;i++)cin>>arr[i];
    vector<query> v;
    for(int i = 1;i<=q;i++){
        query tmp;
        cin>>tmp.l>>tmp.r>>tmp.mood;
        tmp.id = i;
        v.push_back(tmp);
    }
    sort(v.begin(),v.end(),comp);
    int now = n;
    stack<int> st;
    int ans[q+1];
    for(auto qu:v){
        while(now>=qu.l){
            while(st.size()&&arr[now]>arr[st.top()]){
                add(st.top(),arr[st.top()]+arr[now]);
                st.pop();
            }
            while(st.size()&&arr[now]==arr[st.top()])st.pop();
            st.push(now);
            now--;
        }
        ans[qu.id] = (sum(qu.r)<=qu.mood);
    }
    for(int i = 1;i<=q;i++){
        cout<<ans[i]<<"\n";
    }
}

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