Submission #1129473

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129473		notkai	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	64 / 100	3101 ms	246544 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000000
typedef int i1;
i1 n;
vector<i1> arr(MAXN);
vector<vector<i1>> sortedsegment(4*MAXN,vector<i1>(0));
vector<i1> segment(4*MAXN,0);
void calcsorted(i1 treeindex, i1 onleft=0, i1 onright=n-1){
    for (i1 i = onleft; i <= onright; i++){
        sortedsegment[treeindex].push_back(arr[i]);
    }
    sort(sortedsegment[treeindex].begin(), sortedsegment[treeindex].end());
    if (onleft != onright){
        calcsorted(treeindex*2+1, onleft, (onleft+onright)/2);
        calcsorted(treeindex*2+2, (onleft+onright+2)/2, onright);
    }
}
void calcsegtree(i1 treeindex, i1 onleft = 0, i1 onright = n-1){
    if (onleft == onright){
        segment[treeindex] = 0;
        return;
    }
    calcsegtree(treeindex*2+1, onleft, (onleft+onright)/2);
    calcsegtree(treeindex*2+2, (onleft+onright+2)/2, onright);
    segment[treeindex] = max(segment[treeindex*2+1], segment[treeindex*2+2]);
    i1 maxvalue = sortedsegment[treeindex*2+1][sortedsegment[treeindex*2+1].size()-1];
    auto it = lower_bound(sortedsegment[treeindex*2+2].begin(), sortedsegment[treeindex*2+2].end(), maxvalue);
    if (it != sortedsegment[treeindex*2+2].begin()){
        it--;
        segment[treeindex] = max(segment[treeindex], (*it) + maxvalue);
    }
}
i1 greatestlessthan(i1 treeindex, i1 left, i1 right, i1 value,i1 onleft = 0, i1 onright = n-1){
    if (right < onleft || left > onright){
        return -1;
    }
    if (left <= onleft && right >= onright){
        auto it = lower_bound(sortedsegment[treeindex].begin(), sortedsegment[treeindex].end(), value);
        if (it != sortedsegment[treeindex].begin()){
            it--;
            return (*it);
        } else{
            return -1;
        }
    }
    return max(greatestlessthan(treeindex*2+1, left, right, value, onleft, (onleft+onright)/2),greatestlessthan(treeindex*2+2, left, right, value, (onleft+onright+2)/2, onright));
}
i1 greatest(i1 treeindex, i1 left, i1 right, i1 onleft = 0, i1 onright = n-1){
    if (right < onleft || left > onright){
        return -1;
    }
    if (left <= onleft && right >= onright){
        return sortedsegment[treeindex][sortedsegment[treeindex].size()-1];
    }
    return max(greatest(treeindex*2+1, left, right, onleft, (onleft+onright)/2), greatest(treeindex*2+2, left, right, (onleft+onright+2)/2, onright));
}
i1 frcalcsegtree(i1 treeindex, i1 left, i1 right, i1 onleft =0, i1 onright = n-1){
    if (right < onleft || left > onright){
        return -1;
    }
    if (left <= onleft && right >= onright){
        return segment[treeindex];
    }
    i1 answer = max(frcalcsegtree(treeindex*2+1, left, right, onleft, (onleft+onright)/2),frcalcsegtree(treeindex*2+2, left, right, (onleft+onright+2)/2, onright));
    i1 greatestleft = greatest(treeindex*2+1, left, (onleft+onright)/2, onleft, (onleft+onright)/2);
    i1 greatestright = -1;
    if (greatestleft != -1){
        greatestright = greatestlessthan(treeindex*2+2, (onleft+onright+2)/2, right, greatestleft,(onleft+onright+2)/2, onright);
    }
    if (greatestright != -1){
        answer = max(answer, greatestleft + greatestright);
    }
    return answer;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    i1 q; cin >> n >> q;
    for (i1 i = 0; i < n; i++){
        cin >> arr[i];
    }
    calcsorted(0);
    calcsegtree(0);
    for (i1 i = 0; i < q; i++){
        i1 l,r,k; cin >> l >> r >> k;
        l -= 1;
        r -= 1;
        if (frcalcsegtree(0,l,r) > k){
            cout << 0 << "\n";
        } else{
            cout << 1 << "\n";
        }
    }
}

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