Submission #1156547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156547		Rafiullah	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	2025 ms	122324 KiB

sortbooks

#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
const int N = 1e6 + 9;
const int LG = 22;
int a[N],Mx[N<<2], n;
void update(int x,int p,int cur = 1,int st = 1,int en = n){
    if(st==en){
        Mx[cur]=x;
        return;
    }
    int M = (st+en)/2;
    if(st<=p and p<=M)
        update(x, p, cur*2 ,st, M);
    else
        update(x, p, cur*2 + 1 ,M + 1, en);
    Mx[cur]=max(Mx[cur*2],Mx[cur*2+1]);
}
int get(int l,int r,int cur = 1,int st = 1,int en = n){
    if(en<l or st>r)return 0;
    if(l <= st and en <=r)return Mx[cur];
    int M = (st+en) / 2;
    return max(get(l,r,cur * 2,st,M),get(l,r,cur*2+1,M+1,en));
}
void solve(){
    int m;cin>>n>>m;
    vector<vector<int>> T[n+3];
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<int> ans(m + 1);
    for(int i=1;i<=m;i++){
        int l,r,k;
        cin>>l>>r>>k;
        T[r].push_back({l,i,k});
    }
    vector<int> Vec;
    for(int i=1;i<=n;i++){
        while(Vec.size() and a[Vec.back()]<=a[i])
            Vec.pop_back();
        if(Vec.size())
            update(a[Vec.back()]+a[i],Vec.back());
        Vec.push_back(i);
        for(vector<int> j:T[i]){
            int R = get(j[0], i);
            if(R <= j[2])ans[j[1]] = 1;
            else ans[j[1]] = 0;
        }
    }
    for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}  
signed main(){
    int t=1;
    // cin>>t
    while(t--){
        solve();
    }
}

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