제출 #1357243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1357243		Johan	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	13 / 100	435 ms	170320 KiB

sortbooks

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;
int n, m;
long long w[MAXN];
long long bad[MAXN];
long long st[21][MAXN];
int lg[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];

    for (int i = 1; i < n; i++) {
        if (w[i] > w[i+1]) bad[i] = w[i] + w[i+1];
        else bad[i] = 0;
    }

    // build logs
    for (int i = 2; i <= n; i++)
        lg[i] = lg[i/2] + 1;

    // build sparse table
    for (int i = 1; i < n; i++)
        st[0][i] = bad[i];

    for (int j = 1; (1 << j) < n; j++) {
        for (int i = 1; i + (1 << j) - 1 < n; i++) {
            st[j][i] = max(st[j-1][i], st[j-1][i + (1 << (j-1))]);
        }
    }

    while (m--) {
        int l, r;
        long long k;
        cin >> l >> r >> k;

        if (l == r) {
            cout << 1 << '\n';
            continue;
        }

        int len = r - l;
        int j = lg[len];
        long long mx = max(st[j][l], st[j][r - (1 << j)]);

        cout << (mx <= k) << '\n';
    }

    return 0;
}

• 서브태스크 1: 0 / 8
• 서브태스크 2: 0 / 9
• 서브태스크 3: 13 / 13
• 서브태스크 4: 0 / 17
• 서브태스크 5: 0 / 30
• 서브태스크 6: 0 / 23