Submission #398214

#	Time	Username	Problem	Language	Result	Execution time	Memory
398214		definitelynotmee	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++98	0 / 100	727 ms	262148 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 = 0, best = 0;
    vector<int> v;
};
seg* tree[4*MAXN];
void merge(seg*a, seg* b, seg* &ret){
    seg aux = *a;
    ret->v.resize(a->v.size()+b->v.size());
    
    //cerr << "a=>" << a->best << ' ' << a->maxi << '\n' << "b=> " << b->best << ' ' << b->maxi << '\n';
    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);
    }
    ret->best = max(a->best, b->best);
    ret->maxi = max(a->maxi, b->maxi);
    merge(aux.v.begin(), aux.v.end(), b->v.begin(), b->v.end(), ret->v.begin());
    //cerr << "newbest = " << ret->best << ", newmaxi = " <<  ret->maxi << endl; 
}
 
void build(int id, int l, int r, vector<int> &v){
    tree[id] = new seg;
    if(l==r){
        tree[id]->maxi = v[l];
        tree[id]->v.emplace_back(v[l]);
        tree[id]->best = 0;
        return;
    }
    int e = id*2+1;
    int d= id*2+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);
        //cerr << l << ' ' << r << "->" << resp->best << endl;
        return;
    }
    int e = id*2+1;
    int d= id*2+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];
    build(0,0,n-1,v);
 
    for(int i = 0; i < m; i++){
        int a, b, c;
        cin >>a >> b >> c;
        a--;
        b--;
        seg *resp = new seg;
        query(0,0,n-1,a,b,resp);
        cout << (resp->best <= c) << '\n'; 
    }
    
    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