Submission #532508

#	Time	Username	Problem	Language	Result	Execution time	Memory
532508		dannyboy20031204	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1112 ms	143428 KiB

sortbooks

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void db() {cout << '\n';}
template <typename T, typename ...U> void db(T a, U ...b){
    cout << a << ' ', db(b...);
}
const int N = 1e6 + 1;
int pre[N];
void add(int pos, int val){
    for (int i = pos; i < N; i += i & -i) pre[i] = max(pre[i], val);
}
int query(int pos){
    int ans = 0;
    for (int i = pos; i; i -= i & -i) ans = max(ans, pre[i]);
    return ans;
}
int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    cin >> n >> m;
    int a[n + 1], l[m], r[m], x[m], ans[m];
    vector<int> s, v[n + 1], q[n + 1];
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        while (!s.empty() and a[s.back()] <= a[i]) s.pop_back();
        if (!s.empty()) v[s.back()].push_back(i);
        s.push_back(i);
    }
    for (int i = 0; i < m; i++){
        cin >> l[i] >> r[i] >> x[i];
        q[l[i]].push_back(i);
    }
    for (int i = n; i > 0; i--){
        for (int j : v[i]){
            add(j, a[i] + a[j]);
        }
        for (int j : q[i]){
            ans[j] = query(r[j]) <= x[j] ? 1 : 0;
        }
    }
    for (int i : ans) db(i);
}

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