Submission #1284404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284404		adscoding	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	100 / 100	1180 ms	107668 KiB

sortbooks

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b; --i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int maxn = 1e6 + 3;
int n, a[maxn], q;

struct Node
{
    int mx, lz, res;
    Node() {mx = lz = res = -2e9;}
};

Node seg[maxn << 2];

Node combine(const Node &x, const Node &y)
{
    Node res;
    res.mx = max(x.mx, y.mx);
    res.res = max(x.res, y.res);
    return res;
}

void build(int id, int l, int r)
{
    if (l == r)
    {
        seg[id].mx = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r);

    seg[id].mx = max(seg[id << 1].mx, seg[id << 1 | 1].mx);
}

void apply(int id, int val)
{
    seg[id].lz = max(seg[id].lz, val);
    seg[id].res = max(seg[id].res, seg[id].lz + seg[id].mx);
}

void push(int id)
{
    if (seg[id].lz != -2e9)
    {
        apply(id << 1, seg[id].lz); apply(id << 1 | 1, seg[id].lz);
        seg[id].lz = -2e9;
    }
}

void upd(int id, int l, int r, int u, int v, int val)
{
    if (l > v || r < u) return;
    if (l >= u && r <= v) return void(apply(id, val));
    int mid = l + r >> 1;
    push(id);
    upd(id << 1, l, mid, u, v, val); upd(id << 1 | 1, mid + 1, r, u, v, val);
    seg[id] = combine(seg[id << 1], seg[id << 1 | 1]);
}

int get(int id, int l, int r, int u, int v)
{
    if (l > v || r < u) return 0;
    if (l >= u && r <= v) return seg[id].res;
    int mid = l + r >> 1;
    push(id);
    return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}

int ans[maxn];

void solve()
{
    cin >> n >> q;
    FOR(i, 1, n) cin >> a[i];

    build(1, 1, n);

    vector<vector<array<int, 3>>> qrs(n + 1);
    FOR(i, 1, q)
    {
        int l, r, k; cin >> l >> r >> k;
        qrs[l].push_back({r, k, i});
    }

    vector<int> st;
    FORD(l, n, 1)
    {
        while (st.size() && a[st.back()] < a[l]) st.pop_back();

        int pos = n + 1;
        if (st.size())
            pos = st.back();
        if (pos - 1 > l)
        {
            upd(1, 1, n, l + 1, pos - 1, a[l]);
        }

        for (const array<int, 3> &tmp : qrs[l])
        {
            int r = tmp[0], k = tmp[1], id = tmp[2];
            ans[id] = get(1, 1, n, l, r) <= k;
        }

        st.push_back(l);
    }


    FOR(i, 1, q) cout << ans[i] << '\n';
}

signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    #define TASK "TEST"
    if (fopen(TASK".INP", "r"))
    {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }
    solve();
    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         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