Submission #1174281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174281		qrn	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	528 ms	92688 KiB

sortbooks

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define SPEED                     \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
    cout.tie(NULL);

#define pb push_back
#define ins insert
#define fi first
#define se second

#define endl "\n"
#define ALL(x) x.begin(), x.end()
#define sz(x) x.size()
#define intt long long

const intt mod = 1e9 + 7;
const intt base = 31;
const intt inf = 1e9;
const intt mxN = 1e6 + 5;
const intt L = 21;

vector<intt> Bit(mxN), a(mxN), is(mxN);

intt get(intt x) {
    intt res = 0;
    while(x <= mxN) {
        res = max(res, Bit[x]);
        x += (x & -x);
    }
    return res;
}

void upd(intt x, intt delta) {
    while(x > 0) {
        Bit[x] = max(Bit[x], delta);
        x -= (x & -x);
    }
}

void solve() {
    intt n, q;
    cin >> n >> q;
    for(intt i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    vector<vector<pair<intt,pair<intt,intt>>>> qrys(n + 1, vector<pair<intt,pair<intt,intt>>>{});
    for(intt i = 0; i < q; i++) {
        intt l, r, k;
        cin >> l >> r >> k;
        qrys[r].pb({l, {k, i}});
        is[r] = 1;
    }
  
    // for(intt i = 1; i <= n; i++) {
    //     if(qrys[i].empty()) continue;
        
    //     cout << i << " ---------------------- " << endl;
    //     for(pair<intt,pair<intt,intt>>&j : qrys[i]) {
    //         cout << j.fi << " " << j.se.fi << " " << j.se.se << endl;
    //     }
    //     cout << i << " ---------------------- " << endl;
    // }
    
    stack<intt> st;
    vector<intt> ans(q);
    for(intt i = 1; i <= n; i++) {
        if(!st.empty()) {
            intt idx = st.top();
            while(a[i] >= a[idx]) {
                st.pop();
                if(st.empty()) break;
                idx = st.top();
            }
        }
        if(!st.empty()) {
            intt idx = st.top();
            intt delt = a[idx] + a[i];
            upd(idx, delt);
        }
        st.push(i);
        if(is[i]) {
            for(pair<intt,pair<intt,intt>>&j: qrys[i]) {
                intt hey = get(j.fi);
                // cout << j.fi << " " << j.se.fi << " " << j.se.se << ": " << hey << endl;
                if(hey > j.se.fi){
                    ans[j.se.se] = 0;
                } else {
                    ans[j.se.se] = 1;
                }
            }
        }
    }
    
    for(intt i = 0; i < q; i++) {
        cout << ans[i] << endl;
    }
}

signed main() {
    SPEED;
    // sieve();
    intt tst = 1;
    // cin >> tst;
    while (tst--) {
        solve();
    }
}

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