Submission #1183174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183174		Alish	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1160 ms	67612 KiB

sortbooks

#include<bits/stdc++.h>

using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;
typedef long double     ld;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp              make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("input19.txt" , "r" , stdin) ;

const int N = 1e6+23;

int seg[4*N];
int a[N], L[N];
int n, q;
vector<pair<int, pii> > Q[N];
int ans[N];

void upd(int i, int x, int l=1, int r=n+1, int ind=0){
    if(r-l==1){
        seg[ind]=max(seg[ind], x);
        return;
    }
    int mid=(r+l)>>1;
    if(i<mid) upd(i, x, l, mid, 2*ind+1);
    else upd(i, x, mid, r, 2*ind+2);
    seg[ind]=max(seg[2*ind+1], seg[2*ind+2]);
}

int get(int lx, int rx, int l=1, int r=n+1, int ind=0){
    if(lx>=r || rx<=l) return 0;
    if(lx<=l && rx>=r) return seg[ind];
    int mid=(r+l)>>1;
    return max(get(lx, rx, l, mid, 2*ind+1), get(lx, rx, mid, r, 2*ind+2));
}

int main()
{
    fast_io
    cin>>n>>q;
    for (int i=1; i<=n; i++) cin>>a[i];
    vector<int> st;
    for (int i=1; i<=n; i++){
        while(!st.empty() && a[st.back()]<=a[i]) st.pop_back();
        if(!st.empty()) L[i]=st.back();
        st.pb(i);
    }

    for (int i=0; i<q; i++){
        int l, r, k; cin>>l>>r>>k;
        Q[r].pb({i, {l, k}});
    }

    for (int i=1; i<=n; i++){
        if(L[i]) upd(L[i], a[L[i]]+a[i]);
        for (auto pp: Q[i]) ans[pp.F]=(pp.S.S>=get(pp.S.F, i+1));
    }
    for (int i=0; i<q; i++) cout<<ans[i]<<endl;


}

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