제출 #1284185

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284185		adscoding	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++20	13 / 100	915 ms	111964 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, q, a[maxn];

struct Qr
{
    int l, r, k;
} qrs[maxn];

namespace sub12
{
    bool approve()
    {
        return 1ll * q * n <= int(5e7);
    }
    void solve()
    {
        FOR(t, 1, q)
        {
            int ma = -1e9;
            bool c = true;
            FOR(i, qrs[t].l, qrs[t].r)
            {
                if (ma > a[i] && a[i] + ma > qrs[t].k)
                {
                    c = false;
                    break;
                }
                ma = max(ma, a[i]);
            }

            cout << c << '\n';
        }
    }
}

namespace sub3
{
    int pre[maxn];
    bool approve()
    {
        int ma = 1e9;
        FOR(i, 1, n) ma = min(ma, a[i]);
        FOR(i, 1, q) if (ma <= qrs[i].k) return false;
        return true;
    }
    void solve()
    {
        FOR(i, 2, n)
        {
            pre[i] = pre[i - 1];
            if (a[i] < a[i - 1]) ++pre[i];
        }

        FOR(t, 1, q)
        {
            cout << (pre[qrs[t].r] - pre[qrs[t].l] == 0) << '\n';
        }
    }
}

namespace sub56
{
    int seg[maxn << 2];

    void upd(int id, int l, int r, int pos, int val)
    {
        if (l == r) return seg[id] = val, void();
        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 0;
        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<int> g[maxn];
    vector<pair<pair<int, int>, int>> R[maxn];

    bitset<1000001> ans;

    void solve()
    {
        vector<int> st;
        FORD(i, n, 1)
        {
            while (st.size() && a[st.back()] >= a[i]) st.pop_back();
            if (st.size())
            {
                g[st.back()].push_back(i);
            }
            st.push_back(i);
        }

        FOR(i, 1, q)
        {
            R[qrs[i].r].push_back({{qrs[i].l, qrs[i].k}, i});
        }

        FOR(r, 1, n)
        {
            for (int x : g[r]) upd(1, 1, n, x, a[x]);
            for (pair<pair<int, int>, int> tmp : R[r])
            {
                int id = tmp.second, l = tmp.first.first, k = tmp.first.second;
                int ma = get(1, 1, n, l, r);
                ans[id] = ma * 2 <= k;
            }
        }

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

void solve()
{
    cin >> n >> q;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, q) cin >> qrs[i].l >> qrs[i].r >> qrs[i].k;

    sub56 :: solve();
//    if (sub3 :: approve()) sub3 :: solve();
//    else sub12 :: 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;
}

컴파일 시 표준 에러 (stderr) 메시지

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sortbooks.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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