Submission #559351

#	Time	Username	Problem	Language	Result	Execution time	Memory
559351		perchuts	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1427 ms	116464 KiB

sortbooks

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;

const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e6+100;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

int v[maxn], bad[maxn];

struct queries{
    int l, r, k, idx;
}q[maxn];

ii seg[4*maxn];

vector<int>where[maxn];

void build(int i,int l,int r){
    if(l==r){
        seg[i] = {bad[l], bad[l]==0?0:v[l]+v[bad[l]]};
        return;
    }
    int md = (l+r)/2;
    build(2*i,l,md), build(2*i+1,md+1,r);
    if(seg[2*i].second>seg[2*i+1].second)seg[i] = seg[2*i];
    else seg[i] = seg[2*i+1];
}

void update(int i,int l,int r,int x){
    if(l>x||r<x)return;
    if(l==r){
        seg[i] = {0,0};
        return;
    }
    int md = (l+r)/2;
    update(2*i,l,md,x), update(2*i+1,md+1,r,x);
    if(seg[2*i].second>seg[2*i+1].second)seg[i] = seg[2*i];
    else seg[i] = seg[2*i+1];
}

int query(int i,int l,int r,int x,int y){
    if(l>y||r<x)return 0;
    if(x<=l&&r<=y)return seg[i].second;
    int md = (l+r)/2;
    return max(query(2*i,l,md,x,y),query(2*i+1,md+1,r,x,y));
}

bool sorted(queries a,queries b){
    if(a.l==b.l)return a.r<b.r;
    return a.l<b.l;
}

bool answer[maxn];

int main(){_
    int n, m;cin>>n>>m;
    for(int i=1;i<=n;++i)cin>>v[i];    
    for(int i=1;i<=m;++i){
        cin>>q[i].l>>q[i].r>>q[i].k;
        q[i].idx = i;
    }

    stack<ii>st;

    for(int i=1;i<=n;++i){
        while(!st.empty()&&st.top().first<=v[i])st.pop();
        if(!st.empty()){
            bad[i] = st.top().second;
            where[bad[i]].pb(i);
        }
        st.push({v[i],i});
    }

    sort(q+1,q+1+m, sorted);

    int leftPointer = 1;

    build(1,1,n);
    
    for(int i=1;i<=m;++i){
        while(leftPointer<q[i].l){
            for(auto x:where[leftPointer]){
                update(1,1,n,x);
            }
            leftPointer++;
        }
        int mx = query(1,1,n,q[i].l,q[i].r);
        answer[q[i].idx] = mx<=q[i].k;
    }

    for(int i=1;i<=m;++i)cout<<answer[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