Submission #1289229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289229		kiensosad	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	818 ms	327680 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000000;
int st[4*N+2];
void update(int id,int l,int r,int v,int x){
    if(l>v||r<v) return;
    if(l==r){
        st[id]=max(st[id],x);
        return;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,v,x);
    update(id*2+1,mid+1,r,v,x);
    st[id]=max(st[id*2],st[id*2+1]);
}
int get(int id,int l,int r,int u,int v){
    if(l>v||r<u) return 0;
    if(l>=u&&r<=v) return st[id];
    int mid=(l+r)/2;
    return max(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
vector<array<int,3>> g[N+2];
int ans[N+2];
int c[N+2],a[N+2];
int main(){
    #define task ""
    if(fopen(task ".inp", "r")){
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    stack<int> s;
    for(int i=1;i<=n;i++){
        while(!s.empty()&&a[s.top()]<a[i]){
            s.pop();
        }
        if(s.empty()) c[i]=0;
        else c[i]=s.top();
        s.push(i);
    }
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
        int l,r,k;
        cin>>l>>r>>k;
        g[r].push_back({l,k,i});
    }
    for(int i=1;i<=n;i++){
        if(c[i]!=0) {
            update(1,1,n,c[i],a[i]+a[c[i]]);
        }
        for(auto [l,k,id]:g[i]){
            if(get(1,1,n,l,i)<=k) ans[id]=1;
        }
    }
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<"\n";
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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