Submission #527085

#	Time	Username	Problem	Language	Result	Execution time	Memory
527085		jalsol	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++11	100 / 100	1349 ms	97936 KiB

sortbooks

#include <bits/stdc++.h>

using namespace std;

#define Task ""

struct __Init__ {
    __Init__() {
        cin.tie(nullptr)->sync_with_stdio(false);
        if (fopen(Task".inp", "r")) {
            freopen(Task".inp", "r", stdin);
            freopen(Task".out", "w", stdout); }
    }
} __init__;

using ll = long long;

#ifdef LOCAL
#define debug(x) cerr << "[" #x " = " << x << "]\n";
#else
#define debug(...)
#endif // LOCAL

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)

template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxN = 1e6 + 5;

struct Query {
    int r, k, id;
};

int n, nq;
int a[maxN];

vector<Query> q[maxN];
int ans[maxN];

int tree[maxN << 2];

#define m ((l + r) / 2)
#define tl (i << 1)
#define tr (i << 1 | 1)

void update(int p, int x, int i, int l, int r) {
    if (p < l || r < p) return;

    if (l == r) {
        chmax(tree[i], x);
        return;
    }

    update(p, x, tl, l, m);
    update(p, x, tr, m + 1, r);
    tree[i] = max(tree[tl], tree[tr]);
}

int get(int u, int v, int i, int l, int r) {
    if (v < l || r < u) return 0;
    if (u <= l && r <= v) return tree[i];

    return max(get(u, v, tl, l, m), get(u, v, tr, m + 1, r));
}

#undef m
#undef tl
#undef tr

signed main() {
    cin >> n >> nq;
    For (i, 1, n) cin >> a[i];

    For (i, 1, nq) {
        int l, r, k; cin >> l >> r >> k;
        q[l].push_back({r, k, i});
    }

    deque<int> dq;

    Ford (i, n, 1) {
        while (isz(dq) && a[i] > a[dq.front()]) {
            update(dq.front(), a[i] + a[dq.front()], 1, 1, n);
            dq.pop_front();
        }

        dq.push_front(i);

        for (const auto& t : q[i]) {
            ans[t.id] = get(i, t.r, 1, 1, n) <= t.k;
        }
    }

    For (i, 1, nq) {
        cout << ans[i] << '\n';
    }
}

/*

*/

Compilation message (stderr)

sortbooks.cpp: In constructor '__Init__::__Init__()':
sortbooks.cpp:11:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:12:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             freopen(Task".out", "w", stdout); }
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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