oj.uz

Submission #883360

# Submission time Handle Problem Language Result Execution time Memory
883360 2023-12-05T08:08:14 Z boris_mihov Hedgehog Daniyar and Algorithms (IZhO19_sortbooks) C++17
8 / 100
 3000 ms 27732 KB 
#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)
    {
        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;

    for (int i = 1 ; i <= q ; ++i)
    {
        auto [l, r, k, idx] = query[i];
        answer[idx] = true;

        for (int j = l ; j <= r && answer[idx] ; ++j)
        {
            for (int next = j + 1 ; next <= r && answer[idx] ; ++next)
            {
                if (a[j] > a[next] && a[j] + a[next] > k)
                {
                    answer[idx] = false;
                }
            }
        }
    }
}

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

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]++;
      |                       ~~~~~~~~~~^~~
sortbooks.cpp: In function 'void solve()':
sortbooks.cpp:194:9: warning: unused variable 'numsPtr' [-Wunused-variable]
  194 |     int numsPtr = 0;
      |         ^~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6612 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 25 ms 6492 KB Output is correct
9 Correct 11 ms 6748 KB Output is correct
10 Correct 12 ms 6492 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6612 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 25 ms 6492 KB Output is correct
9 Correct 11 ms 6748 KB Output is correct
10 Correct 12 ms 6492 KB Output is correct
11 Correct 17 ms 6492 KB Output is correct
12 Correct 128 ms 6700 KB Output is correct
13 Correct 85 ms 6712 KB Output is correct
14 Correct 197 ms 6764 KB Output is correct
15 Correct 124 ms 6748 KB Output is correct
16 Execution timed out 3056 ms 6492 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 508 ms 27540 KB Output is correct
2 Correct 496 ms 27732 KB Output is correct
3 Correct 538 ms 27684 KB Output is correct
4 Correct 507 ms 27596 KB Output is correct
5 Execution timed out 3046 ms 25680 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3044 ms 8536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6612 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 25 ms 6492 KB Output is correct
9 Correct 11 ms 6748 KB Output is correct
10 Correct 12 ms 6492 KB Output is correct
11 Correct 17 ms 6492 KB Output is correct
12 Correct 128 ms 6700 KB Output is correct
13 Correct 85 ms 6712 KB Output is correct
14 Correct 197 ms 6764 KB Output is correct
15 Correct 124 ms 6748 KB Output is correct
16 Execution timed out 3056 ms 6492 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6612 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 25 ms 6492 KB Output is correct
9 Correct 11 ms 6748 KB Output is correct
10 Correct 12 ms 6492 KB Output is correct
11 Correct 17 ms 6492 KB Output is correct
12 Correct 128 ms 6700 KB Output is correct
13 Correct 85 ms 6712 KB Output is correct
14 Correct 197 ms 6764 KB Output is correct
15 Correct 124 ms 6748 KB Output is correct
16 Execution timed out 3056 ms 6492 KB Time limit exceeded
17 Halted 0 ms 0 KB -