Submission #536436

#	Time	Username	Problem	Language	Result	Execution time	Memory
536436		PiejanVDC	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	17 / 100	3102 ms	262144 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;
 
const int C = 8;
 
vector<int>w;
vector<int>st;
vector<vector<int>>v;
 
void dbg(vector<int>c) {
    for(auto z : c)
        cout << z << " ";
    cout << "\n\n";
}
 
void build(int i_, int j_, int p_) {
    if(i_ == j_) {
        st[p_] = 0;
        v[p_].push_back(w[i_]);
        return;
    }
    int mid_ = (i_ + j_) >> 1;
    build(i_, mid_, 2 * p_);
    build(mid_ + 1, j_, 2 * p_ + 1);
    int mx = max(st[2 * p_], st[2 * p_ + 1]);
    int p = 0;
  	const int MAX = (v[2 * p_].empty() ? 0 : v[2 * p_].back());
    for(int i = 0 ; i < (int)v[2 * p_].size() ; i++) {
        while(p < (int)v[2 * p_ + 1].size() && v[2 * p_ + 1][p] < v[2 * p_][i]) {
            v[p_].push_back(v[2 * p_ + 1][p]);
            mx = max(mx, MAX + v[p_].back());
            p++;
        }
        v[p_].push_back(v[2 * p_][i]);
    }
    while(p < (int)v[2 * p_ + 1].size())
        v[p_].push_back(v[2 * p_ + 1][p]), p++;
    st[p_] = mx;
}
 
int l_, r_;
int ans;
 
vector<int>query(int i_, int j_, int p_) {
    if(i_ > r_ || j_ < l_)
        return {};
    if(i_ >= l_ && j_ <= r_) {
        ans = max(ans, st[p_]);
        return v[p_];
    }
    int mid_ = (i_ + j_) >> 1;
    vector<int>v1 = query(i_, mid_, 2 * p_),
               v2 = query(mid_ + 1, j_, 2 * p_ + 1),
               v3;
    int p = 0;
    const int MAX = (v1.empty() ? 0 : v1.back());
    for(int i = 0 ; i < (int)v1.size() ; i++) {
        while(p < (int)v2.size() && v2[p] < v1[i]) {
            v3.push_back(v2[p]);
            ans = max(ans, MAX + v3.back());
            p++;
        }
        v3.push_back(v1[i]);
    }
    while(p < (int)v2.size())
        v3.push_back(v2[p++]);
    return v3;
}
 
signed main() {
    int N,Q;
    scanf("%d%d", &N, &Q);
    w.resize(N);
    st.resize(C * N);
    v.resize(C * N);
    for(auto &in : w)
        scanf("%d", &in);
    build(0, N-1, 1);
    while(Q--) {
        int l,r,k;
        scanf("%d%d%d", &l, &r, &k);
        l--,r--;
        l_ = l, r_ = r, ans = 0;
        query(0, N-1, 1);
        cout << (ans <= k) << "\n";
    }
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d%d", &N, &Q);
      |     ~~~~~^~~~~~~~~~~~~~~~
sortbooks.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%d", &in);
      |         ~~~~~^~~~~~~~~~~
sortbooks.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%d%d%d", &l, &r, &k);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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