oj.uz

Submission #924576

# Submission time Handle Problem Language Result Execution time Memory
924576 2024-02-09T08:28:45 Z boris_mihov Financial Report (JOI21_financial) C++17
31 / 100
 2379 ms 30548 KB 
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
#include <cmath>
#include <set>

typedef long long llong;
const int MAXN = 300000 + 10;
const int INF  = 1e9;

int n, d;
struct SegmentTree
{
    struct Node
    {
        int length;
        int prefixOnes;
        int suffixOnes;
        int maxOnes;
        int maxDP;

        Node()
        {
            prefixOnes = suffixOnes = maxOnes = maxDP = length = 0;
        }

        friend Node operator + (const Node &left, const Node &right)
        {
            Node res;
            res.length = left.length + right.length;
            
            res.prefixOnes = left.prefixOnes;
            if (left.prefixOnes == left.length) res.prefixOnes = left.length + right.prefixOnes;

            res.suffixOnes = right.suffixOnes;
            if (right.suffixOnes == right.length) res.suffixOnes = right.length + left.suffixOnes;
            
            res.maxOnes = left.suffixOnes + right.prefixOnes;
            res.maxOnes = std::max(res.maxOnes, left.maxOnes);
            res.maxOnes = std::max(res.maxOnes, right.maxOnes);
            res.maxDP = std::max(left.maxDP, right.maxDP);
            return res;
        }
    };

    Node tree[4*MAXN];
    void update(int l, int r, int node, int queryPos, int dpVAL)
    {
        if (l == r)
        {
            tree[node].maxDP = dpVAL;
            tree[node].prefixOnes = 1;
            tree[node].suffixOnes = 1;
            tree[node].maxOnes = 1;
            tree[node].length = 1;
            return;
        }

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

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

        Node res;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = res + query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) res = 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 queryOnes(int l, int r)
    {
        return query(1, n, 1, l, r).maxOnes;
    }

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

int a[MAXN];
int dp[MAXN];
int perm[MAXN];
SegmentTree tree;

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] || (a[x] == a[y] && x < y);
    });

    int res = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        int l = perm[i], r = n, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (tree.queryOnes(perm[i] + 1, mid) < d) l = mid;
            else r = mid;
        }

        dp[perm[i]] = tree.queryDP(perm[i] + 1, r) + 1;
        tree.update(perm[i], dp[perm[i]]);
        res = std::max(res, dp[perm[i]]);
    }

    std::cout << res << '\n';
}

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

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

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

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 5 ms 27480 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27248 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 5 ms 27228 KB Output is correct
10 Correct 5 ms 27228 KB Output is correct
11 Correct 5 ms 27228 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 5 ms 27288 KB Output is correct
15 Correct 5 ms 27228 KB Output is correct
16 Correct 5 ms 27264 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 6 ms 27228 KB Output is correct
19 Correct 6 ms 27224 KB Output is correct
20 Correct 5 ms 27228 KB Output is correct
21 Correct 5 ms 27228 KB Output is correct
22 Correct 5 ms 27228 KB Output is correct
23 Correct 5 ms 27228 KB Output is correct
24 Correct 6 ms 27228 KB Output is correct
25 Correct 5 ms 27224 KB Output is correct
26 Correct 5 ms 27228 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 5 ms 27480 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27248 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 5 ms 27228 KB Output is correct
10 Correct 5 ms 27228 KB Output is correct
11 Correct 5 ms 27228 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 5 ms 27288 KB Output is correct
15 Correct 5 ms 27228 KB Output is correct
16 Correct 5 ms 27264 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 6 ms 27228 KB Output is correct
19 Correct 6 ms 27224 KB Output is correct
20 Correct 5 ms 27228 KB Output is correct
21 Correct 5 ms 27228 KB Output is correct
22 Correct 5 ms 27228 KB Output is correct
23 Correct 5 ms 27228 KB Output is correct
24 Correct 6 ms 27228 KB Output is correct
25 Correct 5 ms 27224 KB Output is correct
26 Correct 5 ms 27228 KB Output is correct
27 Correct 7 ms 27228 KB Output is correct
28 Incorrect 6 ms 27228 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 5 ms 27480 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27248 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 5 ms 27228 KB Output is correct
10 Correct 5 ms 27228 KB Output is correct
11 Correct 5 ms 27228 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 5 ms 27288 KB Output is correct
15 Correct 5 ms 27228 KB Output is correct
16 Correct 5 ms 27264 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 6 ms 27228 KB Output is correct
19 Correct 6 ms 27224 KB Output is correct
20 Correct 5 ms 27228 KB Output is correct
21 Correct 5 ms 27228 KB Output is correct
22 Correct 5 ms 27228 KB Output is correct
23 Correct 5 ms 27228 KB Output is correct
24 Correct 6 ms 27228 KB Output is correct
25 Correct 5 ms 27224 KB Output is correct
26 Correct 5 ms 27228 KB Output is correct
27 Correct 7 ms 27228 KB Output is correct
28 Incorrect 6 ms 27228 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2091 ms 27444 KB Output is correct
2 Correct 1568 ms 30012 KB Output is correct
3 Correct 1700 ms 30356 KB Output is correct
4 Correct 1824 ms 30352 KB Output is correct
5 Correct 1620 ms 30352 KB Output is correct
6 Correct 1768 ms 30352 KB Output is correct
7 Correct 1351 ms 30328 KB Output is correct
8 Correct 2019 ms 30368 KB Output is correct
9 Correct 1401 ms 30544 KB Output is correct
10 Correct 1703 ms 30348 KB Output is correct
11 Correct 1540 ms 30288 KB Output is correct
12 Correct 1641 ms 30348 KB Output is correct
13 Correct 1646 ms 30356 KB Output is correct
14 Correct 1832 ms 30548 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2037 ms 27444 KB Output is correct
2 Correct 2222 ms 30312 KB Output is correct
3 Correct 2307 ms 30544 KB Output is correct
4 Correct 2360 ms 30356 KB Output is correct
5 Correct 2327 ms 30548 KB Output is correct
6 Correct 2328 ms 30288 KB Output is correct
7 Correct 2041 ms 30348 KB Output is correct
8 Correct 2011 ms 30380 KB Output is correct
9 Correct 2023 ms 30328 KB Output is correct
10 Correct 2323 ms 30344 KB Output is correct
11 Correct 2379 ms 30352 KB Output is correct
12 Correct 2239 ms 30352 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 27224 KB Output is correct
2 Correct 5 ms 27480 KB Output is correct
3 Correct 5 ms 27228 KB Output is correct
4 Correct 5 ms 27228 KB Output is correct
5 Correct 5 ms 27228 KB Output is correct
6 Correct 5 ms 27248 KB Output is correct
7 Correct 5 ms 27228 KB Output is correct
8 Correct 5 ms 27228 KB Output is correct
9 Correct 5 ms 27228 KB Output is correct
10 Correct 5 ms 27228 KB Output is correct
11 Correct 5 ms 27228 KB Output is correct
12 Correct 5 ms 27228 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 5 ms 27288 KB Output is correct
15 Correct 5 ms 27228 KB Output is correct
16 Correct 5 ms 27264 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 6 ms 27228 KB Output is correct
19 Correct 6 ms 27224 KB Output is correct
20 Correct 5 ms 27228 KB Output is correct
21 Correct 5 ms 27228 KB Output is correct
22 Correct 5 ms 27228 KB Output is correct
23 Correct 5 ms 27228 KB Output is correct
24 Correct 6 ms 27228 KB Output is correct
25 Correct 5 ms 27224 KB Output is correct
26 Correct 5 ms 27228 KB Output is correct
27 Correct 7 ms 27228 KB Output is correct
28 Incorrect 6 ms 27228 KB Output isn't correct
29 Halted 0 ms 0 KB -