oj.uz

Submission #536230

# Submission time Handle Problem Language Result Execution time Memory
536230 2022-03-12T16:07:42 Z PiejanVDC Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
0 / 100
 3000 ms 262144 KB 
#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;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Incorrect 3 ms 428 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Incorrect 3 ms 428 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 321 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3079 ms 38184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Incorrect 3 ms 428 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 468 KB Output is correct
8 Correct 3 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Incorrect 3 ms 428 KB Output isn't correct
11 Halted 0 ms 0 KB -