Submission #883369

#	Time	Username	Problem	Language	Result	Execution time	Memory
883369		boris_mihov	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	100 / 100	1939 ms	159832 KiB

sortbooks

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <vector>
#include <bitset>
#include <queue>
#include <set>

typedef long long llong;
const int MAXN = 1000000 + 10;
const int MAXLOG = 20;

const llong INF = 4e18;
const int INTINF = 2e9;

int n, q;
struct Sparse
{
    int sparse[MAXLOG][MAXN];
    int getLog[MAXN];

    void build(int a[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            sparse[0][i] = a[i];
        }

        for (int log = 1 ; (1 << log) <= n ; ++log)
        {
            for (int i = 1 ; i + (1 << log) - 1 <= n ; ++i)
            {
                sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
            }
        }

        for (int i = 1 ; i <= n ; ++i)
        {
            getLog[i] = getLog[i - 1];
            if ((1 << getLog[i] + 1) < i) getLog[i]++;
        }
    }

    int findMAX(int l, int r)
    {
        assert(l - 1 <= r);
        if (l > r) return -INTINF;
        int log = getLog[r - l + 1];
        return std::max(sparse[log][l], sparse[log][r - (1 << log) + 1]);
    }
};

struct Fenwick
{
    int tree[MAXN];
    void update(int pos, int value)
    {
        for (int idx = pos ; idx <= n ; idx += idx & (-idx))
        {
            tree[idx] += value;
        }
    }

    int query(int pos)
    {
        int res = 0;
        for (int idx = pos ; idx > 0 ; idx -= idx & (-idx))
        {
            res += tree[idx];
        }

        return res;
    }

    void reset(int pos)
    {
        update(pos, -query(pos) + query(pos - 1));
    }

    int findKth(int k)
    {
        int pos = 0;
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (pos + (1 << log) <= n && tree[pos + (1 << log)] < k)
            {
                pos += (1 << log);
                k -= tree[pos];
            }
        }

        return pos + 1;
    }
};

struct SegmentTree
{
    int tree[4*MAXN];
    void update(int l, int r, int node, int queryPos, int queryVal)
    {
        if (l == r)
        {
            tree[node] = queryVal;
            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos, queryVal);
        else update(mid + 1, r, 2*node + 1, queryPos, queryVal);
        tree[node] = std::max(tree[2*node], tree[2*node + 1]);
    }

    int query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

        int res = 0;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = std::max(res, query(l, mid, 2*node, queryL, queryR));
        if (mid + 1 <= queryR) res = std::max(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
        return res;
    }

    void update(int pos, int val)
    {
        update(1, n, 1, pos, val);
    }

    int query(int l, int r)
    {
        return query(1, n, 1, l, r);
    }
};

struct Query
{
    int l, r, k, idx;
    friend bool operator > (const Query &a, const Query &b)
    {
        return a.k > b.k;
    }
};

int a[MAXN];
int perm[MAXN];
bool answer[MAXN];
Query query[MAXN];
SegmentTree tree;
Fenwick active;
Fenwick sorted;
Sparse sparse;

void addNum(int idx)
{
    int cntTo = active.query(idx - 1);
    if (cntTo > 0)
    {
        int prev = active.findKth(cntTo);
        sorted.reset(prev);
        if (a[prev] > a[idx]) sorted.update(prev, 1);
        tree.update(prev, sparse.findMAX(prev + 1, idx - 1) + a[prev]);
    }

    if (active.query(n) == cntTo)
    {
        tree.update(idx, sparse.findMAX(idx + 1, n) + a[idx]);
    } else
    {
        int next = active.findKth(cntTo + 1);
        tree.update(idx, sparse.findMAX(idx + 1, next - 1) + a[idx]);
        if (a[idx] > a[next])
        {
            sorted.update(idx, 1);
        }
    }

    active.update(idx, 1);
}

void solve()
{
    std::iota(perm + 1, perm + 1 + n, 1);
    std::sort(perm + 1, perm + 1 + n, [&](int x, int y)
    {
        return a[x] > a[y];
    });

    std::sort(query + 1, query + 1 + q, std::greater <Query> ());
    int numsPtr = 0;

    sparse.build(a);
    for (int i = 1 ; i <= q ; ++i)
    {
        auto [l, r, k, idx] = query[i];
        while (numsPtr + 1 <= n && 2 * a[perm[numsPtr + 1]] > k)
        {
            numsPtr++;
            addNum(perm[numsPtr]);
        }

        int toL = active.query(l - 1);
        int toR = active.query(r);

        if (toL == toR)
        {
            answer[idx] = true;
            continue;
        } 

        int posL = active.findKth(toL + 1);
        int posR = active.findKth(toR);

        assert(l <= posL && posL <= posR && posR <= r);
        if (sorted.query(posR - 1) - sorted.query(posL - 1) > 0)
        {
            answer[idx] = false;
            continue;
        }

        int res = 0;
        if (posR < r)
        {
            res = std::max(res, a[posR] + sparse.findMAX(posR + 1, r));
        }

        if (posL < posR) res = std::max(res, tree.query(posL, posR - 1));
        answer[idx] = (res <= k);
    }
}

void print()
{
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cout << answer[i] << '\n';
    }
}

void input()
{
    std::cin >> n >> q;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }

    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> query[i].l >> query[i].r >> query[i].k;
        query[i].idx = i;
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

Compilation message (stderr)

sortbooks.cpp: In member function 'void Sparse::build(int*)':
sortbooks.cpp:35:93: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   35 |                 sparse[log][i] = std::max(sparse[log - 1][i], sparse[log - 1][i + (1 << log - 1)]);
      |                                                                                         ~~~~^~~
sortbooks.cpp:42:33: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   42 |             if ((1 << getLog[i] + 1) < i) getLog[i]++;
      |                       ~~~~~~~~~~^~~

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