Submission #1266858

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266858		trinm01	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	0 / 100	883 ms	73628 KiB

sortbooks

// #pragma GCC optimize("O3")
// #pragma GCC optimization("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;

#define int long long 
#define ll long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)
#define FOD(i, r, l) for (int i = (r); i >= (l); i--)
#define fi first
#define se second
#define pii pair<int, int>

const ll mod = 1e9 + 7;
const int MAXN = 1e6 + 5;
const ll oo = 1e18+7;  
const int base = 10;

int n, q, a[MAXN];
struct query{
    int l, r, k, id;
}tv[MAXN];
int res[MAXN];
bool cmp(query a, query b){
    return a.r<b.r;
}

int st[4*MAXN];
void update(int id, int l, int r, int i, int val){
    if(l>i || r<i){
        return;
    }
    if(l>=r){
        st[id]=max(st[id], val);
        return;
    }
    int mid=(l+r)/2;
    update(id*2, l, mid, i, val);
    update(id*2+1, mid+1, r, i, val);
    st[id]=max(st[id*2], st[id*2+1]);
}
int get(int id, int l, int r, int i, int j){
    if(l>j || r<i){
        return 0;
    }
    if(l>=i && r<=j){
        return st[id];
    }
    int mid=(l+r)/2;
    return max(get(id*2, l, mid, i, j), get(id*2+1, mid+1, r, i, j));
}

stack<int> stk;
int lft[MAXN];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if(fopen(".inp", "r")){
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }   

    cin >> n >> q;
    FOR(i, 1, n){
        cin >> a[i];
    }
    FOR(i, 1, q){
        int l, r, k;
        cin >> l >> r >> k;
        tv[i]={l, r, k, i};
    }

    a[0]=oo;
    stk.push(0);
    FOR(i, 1, n){
        while(!stk.empty() && a[stk.top()]<a[i]){
            stk.pop();
        }
        lft[i]=stk.top();
        stk.push(i);
    }

    int j=1;
    FOR(i, 1, q){
        auto [l, r, k, id]=tv[i];
        while(j<=r){
            update(1, 1, n, lft[j], a[lft[j]]+a[j]);
            j++;
        }
        if(get(1, 1, n, l, r)<=k){
            res[id]=1;
        }
        else{
            res[id]=0;
        }
    }

    FOR(i, 1, q){
        cout << res[i] << '\n';
    }
    
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen(".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