제출 #536230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
536230		PiejanVDC	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	0 / 100	3079 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;
    vector<int>MAX((int)v[2 * p_].size());
    int CURR_MAX = 0;
    for(int i = (int)v[2 * p_].size()-1 ; i >= 0 ; i--)
        CURR_MAX = max(CURR_MAX, v[2 * p_][i]), MAX[i] = CURR_MAX;
    auto dist = [&] (int P, int add_) -> int {
        return MAX[P] + add_;
    };
    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, dist(i, 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;
    vector<int>MAX((int)v1.size());
    int CURR_MAX = 0;
    for(int i = (int)v1.size()-1 ; i >= 0 ; i--)
        CURR_MAX = max(CURR_MAX, v1[i]), MAX[i] = CURR_MAX;
    auto dist = [&] (int P, int add_) -> int {
        return MAX[P] + add_;
    };
    //dbg(v1), dbg(v2);
    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, dist(i, 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;
        auto x = query(0, N-1, 1);
        cout << (ans <= k) << "\n";
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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

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