제출 #1093237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1093237		andrewp	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++14	100 / 100	770 ms	71660 KiB

sortbooks

//Dedicated to my love, ivaziva
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h> 
using namespace std;  
 
using pii = pair<int, int>;
using ll = int64_t;
 
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define dbg(x) cerr << #x << ": " << x << '\n'; 

const int N = 1e6 + 20;
int maxi[4*N];

void updateMax(int v,int tl,int tr,int i,int x){
    if(tl==tr){
        maxi[v]=x;
        return;
    }
    int mid=(tl+tr)/2;
    if(i<=mid) updateMax(2*v,tl,mid,i,x);
    else updateMax(2*v+1,mid+1,tr,i,x);
    maxi[v]=max(maxi[2*v],maxi[2*v+1]);
}
int Max(int v,int tl,int tr,int l,int r){
    if(l>r) return 0;
    if(tl==l&&tr==r) return maxi[v];
    int mid=(tl+tr)/2;
    return max(Max(2*v,tl,mid,l,min(mid,r)),Max(2*v+1,mid+1,tr,max(mid+1,l),r));
}

struct qry {
    int l, r, k, i;
};

bool cmp(qry x, qry y) {
    return x.r < y.r;
}
 
int32_t main()  {
    ios::sync_with_stdio(false); cin.tie(nullptr);  
    cout.tie(nullptr); cerr.tie(nullptr);
 
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }   
    stack<int> stk;
    vector<int> b(n + 1);
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && a[i] >= a[stk.top()]) {
            stk.pop();
        }
        if (!stk.empty()) {
            b[i] = stk.top();
        }
        stk.push(i);
    }
    vector<qry> qu;
    for (int i = 1; i <= q; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        qu.push_back({l, r, k, i});
    }
    sort(all(qu), cmp);
    int j = 1;
    vector<int> ans(q + 1, 0);
    for (auto x : qu) {
        while (j <= x.r) {
            if (b[j] == 0) {
                ;
            }
            else {
                updateMax(1, 1, n, b[j], a[j] + a[b[j]]);
            }
            j++;
        }
        ans[x.i] = Max(1, 1, n, x.l, x.r);
        if (ans[x.i] <= x.k) {
            ans[x.i] = 1;
        } else {
            ans[x.i] = 0;
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
    return 0;   
}

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