Submission #1058885

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058885		vjudge1	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	598 ms	71764 KiB

sortbooks

#include <bits/stdc++.h>
#ifdef LOCAL
    #include "/home/trcmai/code/tools.h"
    #define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
#else
    #define debug(x...)
#endif
using namespace std;
#define all(a) a.begin(), a.end()
#define ll long long
#define endl '\n'
const int N = 1e6 + 6, LOG = 27, MOD = 1e9 + 7;
const ll INF = 1e18;
int n,q,jmp[N]; 
ll w[N];
vector<tuple<int,int,ll>>Q[N];

template<class T> struct segtree_max {
    int n;
    vector<T> t;
    T merge(T a, T b) {return max(a, b);}
    void init(int N) {n = N; t.assign(2*n, numeric_limits<T>::min());}
    void set(int i, T v) {
        for (t[i+=n] = v; i > 1; i>>=1) t[i >> 1] = merge(t[i], t[i^1]);
    }
    void build(const vector<T> &a) {
        for (int i = 0; i < n; i++) set(i, a[i]);
    }
    T get(int l, int r) {
        r++;
        T x = numeric_limits<T>::min();
        for (l+=n, r+=n; l < r; l>>=1, r>>=1) {
            if (l & 1) x = merge(x, t[l++]);
            if (r & 1) x = merge(x, t[--r]);
        }
        return x;
    }
};

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    auto solver=[&](){
        cin>>n>>q;
        deque<int>dq;
        for(int i = 1;i <= n;++i){ 
            cin>>w[i];
            while(dq.size() && w[dq.back()] <= w[i]) dq.pop_back();
            if(dq.size()) jmp[i] = dq.back();
            dq.push_back(i);
        }
        for(int i = 1;i <= q;++i){
            int l,r; ll c; 
            cin>>l>>r>>c;
            Q[r].emplace_back(i,l,c);
        }
        vector<bool>res(q + 1,false);
        segtree_max<int> st; st.init(n + 5);
        for(int i = 1;i <= n;++i){ 
            st.set(jmp[i],w[i] + w[jmp[i]]);
            for(auto [idx,l,c] : Q[i])
                res[idx] = (st.get(l,i) <= c);
        }
        for(int i = 1;i <= q;++i)
            cout<<res[i]<<endl;
    };
    int t = 1; // cin>>t;
    while (t--) solver();
}

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