Submission #1301792

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

sortbooks

#include <bits/stdc++.h>
#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)
#define all(x) x.begin(), x.end()
#define uni(x) sort(all(x)), x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define dbg(...) debug(#__VA_ARGS__, __VA_ARGS__)

template<typename T>
void _print_one(const char *&s, const T &v)
{
    while (*s == ' ') ++s;
    const char *p = s;
    while (*s && *s != ',') ++s;
    cerr.write(p, s - p) << " = " << v;
    if (*s == ',')
    {
        cerr << "  ,  ";
        ++s;
    }
}
template<typename... Args>
void debug(const char *s, Args... args)
{
    cerr << "[  ";
    int dummy[] = {0, (_print_one(s, args), 0)...};
    (void)dummy;
    cerr << "  ]\n\n";
}


// -----------------------------------------------------------------------------------

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

// -----------------------------------------------------------------------------------


namespace AC
{
    int seg[maxn << 2];
    void upd(int id, int l, int r, int pos, int val)
    {
        if (l == r) return void(seg[id] = max(seg[id], val));
        int mid = l + r >> 1;
        if (pos <= mid) upd(id << 1, l, mid, pos, val);
        else upd(id << 1 | 1, mid + 1, r, pos, val);
        seg[id] = max(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 -1e9;
        if (l >= u && r <= v) return seg[id];
        int mid = l + r >> 1;
        return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
    }

    vector<array<int, 3>> qrs[maxn];
    int ans[maxn];

    void solve()
    {
        FOR(iq, 1, q)
        {
            int l, r, k; cin >> l >> r >> k;
            qrs[r].push_back({l, k, iq});
        }

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

            if (st.size())
            {
                int x = st.back();
                upd(1, 1, n, x, a[x] + a[r]);
            }

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

            st.push_back(r);
        }

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

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

    AC :: solve();
}

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