제출 #398205

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
398205		definitelynotmee	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++98	17 / 100	519 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];
seg* merge(seg* a, seg* b){
    seg* ret = new seg;
    ret->v.resize(a->v.size()+b->v.size());
    ret->best = max(a->best, b->best);
    ret->maxi = max(a->maxi, b->maxi);
    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);
    }
    merge(a->v.begin(), a->v.end(), b->v.begin(), b->v.end(), ret->v.begin());
    return ret;
}

void build(int id, int l, int r, vector<int> &v){
    if(l==r){
        tree[id] = new seg;
        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);
    tree[id] = merge(tree[e],tree[d]);
}

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

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 = *query(0,0,n-1,a,b);
        cout << (resp.best <= c) << '\n'; 
    }
    
    return 0;

}

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