Submission #1267810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267810		minhpk	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	1167 ms	98260 KiB

sortbooks

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int z[1000005];
struct query{
    int l,k,id;
};
vector <query> pos[1000005];
int prv[1000005];

int f[4000005];
int res[1000005];

void update(int id,int l,int r,int pos,int val){
    if (l==r){
        f[id]=max(f[id],val);
        return;
    }
    int mid=(l+r)/2;
    if (pos<=mid){
        update(id*2,l,mid,pos,val);
    }else{
        update(id*2+1,mid+1,r,pos,val);
    }
    f[id]=max(f[id*2],f[id*2+1]);
}
int get(int id,int l,int r,int x,int y){
    if (x>r || y<l){
        return 0;
    }
    if (l>=x && y>=r){
        return f[id];
    }
    int mid=(l+r)/2;
    return max(get(id*2,l,mid,x,y),get(id*2+1,mid+1,r,x,y));
}
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=a;i++){
         cin >> z[i];
    }
    for (int i=1;i<=b;i++){
         int l,r,k;
         cin >> l >> r >> k;
         pos[r].push_back({l,k,i});
    }
    stack<int> st;
    for (int i=1;i<=a;i++){
         while (st.size() && z[i]>z[st.top()]){
               st.pop();
         }
         if (st.size()){
             prv[i]=st.top();
         }
         st.push(i);
    }
    for (int i=1;i<=a;i++){
         if (prv[i]){
             int val=z[i]+z[prv[i]];
             update(1,1,a,prv[i],val);
         }
         for (auto [l,k,id]:pos[i]){
              int val=get(1,1,a,l,i);
              if (val>k){
                  res[id]=0;
              }else{
                  res[id]=1;
              }
         }
    }
    for (int i=1;i<=b;i++){
         cout << res[i] << "\n";
    }
    return 0;
}

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