Submission #398234

#	Time	Username	Problem	Language	Result	Execution time	Memory
398234		definitelynotmee	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++98	0 / 100	210 ms	132624 KiB

sortbooks

#include <bits/stdc++.h>
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MAXN = 1000001;

struct seg{
    int maxi, best;
    vector<int> v;
};
seg tree[4*MAXN];

inline void merge(seg a, seg b, seg&ret){


    ret.v.reserve(a.v.size() + b.v.size());
    ret.maxi = max(a.maxi, b.maxi);
    ret.best = max(a.best, b.best);

    auto it = lower_bound(b.v.begin(),b.v.end(),a.maxi);
    if(it!=b.v.begin()){
        it--;
        ret.best = max(ret.best, *it+a.maxi);
    }

}

void build(int id, int l, int r, vector<int> & v){
    if(l==r){
        tree[id].maxi = v[l];
        tree[id].best = 0;
        tree[id].v.emplace_back(v[l]);
        return;
    }
    int e = 2*id+1;
    int d = 2*id+2;
    int m = (l+r)>>1;
    build(e,l,m,v);
    build(d,m+1,r,v);
    merge(tree[e],tree[d],tree[id]);
}

void query(int id, int l, int r, int ql, int qr, seg&resp){
    if(l>qr || r < ql)
        return;
    if(ql<=l && r <= qr){
        merge(resp,tree[id],resp);
        return;
    }
    int e = 2*id+1;
    int d = 2*id+2;
    int m = (l+r)>>1;
    query(e,l,m,ql,qr,resp);
    query(d,m+1,r,ql,qr,resp);
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m;
    cin >> n >> m;
    vector<int> v(n);
    for(int i = 0; i < n; i++)
        cin >> v[i];
    if(n<=1e5){
        build(0,0,n-1,v);

        for(int i = 0; i < m; i++){
            int a, b, c;
            cin >> a>> b >> c;
            a--, b--;
            seg cur;
            query(0,0,n-1,a,b,cur);
            cout <<  (cur.best <= c) << '\n';
        }
    } /*else {
        vector<vector<int>> sparse(n,vector<int>(25));
        set<int,greater<int>> s;
        vector<int> order(n);
        iota(order.begin(),order.end(),0);
        sort(order.begin(),order.end(),[&](int a, int b){return v[a]<v[b];});
        for(int i = 0; i < n; i++){
            auto aux = s.insert(order[i]);
            aux.first--;
            sparse[order[i]][0] = *aux.first;
        }
        for(int i = 1; i < 25; i++){
            for(int j = 0; j < n; j++){

            }
        }
    }*/
    return 0;

}

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