oj.uz

Submission #924580

# Submission time Handle Problem Language Result Execution time Memory
924580 2024-02-09T08:30:46 Z boris_mihov Financial Report (JOI21_financial) C++17
31 / 100
 2344 ms 27472 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)
    {
        if (l > r) return 0;
        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 27228 KB Output is correct
3 Correct 5 ms 27256 KB Output is correct
4 Correct 5 ms 27224 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct
6 Correct 5 ms 27304 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 27260 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 27272 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 6 ms 27228 KB Output is correct
15 Correct 5 ms 27308 KB Output is correct
16 Correct 5 ms 27228 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 5 ms 27228 KB Output is correct
19 Correct 5 ms 27228 KB Output is correct
20 Correct 5 ms 27264 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 27224 KB Output is correct
24 Correct 5 ms 27260 KB Output is correct
25 Correct 5 ms 27228 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 27228 KB Output is correct
3 Correct 5 ms 27256 KB Output is correct
4 Correct 5 ms 27224 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct
6 Correct 5 ms 27304 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 27260 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 27272 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 6 ms 27228 KB Output is correct
15 Correct 5 ms 27308 KB Output is correct
16 Correct 5 ms 27228 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 5 ms 27228 KB Output is correct
19 Correct 5 ms 27228 KB Output is correct
20 Correct 5 ms 27264 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 27224 KB Output is correct
24 Correct 5 ms 27260 KB Output is correct
25 Correct 5 ms 27228 KB Output is correct
26 Correct 5 ms 27228 KB Output is correct
27 Correct 6 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 27228 KB Output is correct
3 Correct 5 ms 27256 KB Output is correct
4 Correct 5 ms 27224 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct
6 Correct 5 ms 27304 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 27260 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 27272 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 6 ms 27228 KB Output is correct
15 Correct 5 ms 27308 KB Output is correct
16 Correct 5 ms 27228 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 5 ms 27228 KB Output is correct
19 Correct 5 ms 27228 KB Output is correct
20 Correct 5 ms 27264 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 27224 KB Output is correct
24 Correct 5 ms 27260 KB Output is correct
25 Correct 5 ms 27228 KB Output is correct
26 Correct 5 ms 27228 KB Output is correct
27 Correct 6 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 1980 ms 27448 KB Output is correct
2 Correct 1552 ms 27440 KB Output is correct
3 Correct 1617 ms 27448 KB Output is correct
4 Correct 1866 ms 27440 KB Output is correct
5 Correct 1623 ms 27448 KB Output is correct
6 Correct 1730 ms 27452 KB Output is correct
7 Correct 1325 ms 27464 KB Output is correct
8 Correct 2005 ms 27224 KB Output is correct
9 Correct 1369 ms 27440 KB Output is correct
10 Correct 1714 ms 27440 KB Output is correct
11 Correct 1585 ms 27440 KB Output is correct
12 Correct 1580 ms 27448 KB Output is correct
13 Correct 1617 ms 27448 KB Output is correct
14 Correct 1782 ms 27448 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1981 ms 27444 KB Output is correct
2 Correct 2127 ms 27444 KB Output is correct
3 Correct 2258 ms 27440 KB Output is correct
4 Correct 2270 ms 27440 KB Output is correct
5 Correct 2204 ms 27472 KB Output is correct
6 Correct 2344 ms 27444 KB Output is correct
7 Correct 2057 ms 27444 KB Output is correct
8 Correct 2007 ms 27444 KB Output is correct
9 Correct 1985 ms 27436 KB Output is correct
10 Correct 2136 ms 27440 KB Output is correct
11 Correct 2243 ms 27444 KB Output is correct
12 Correct 2202 ms 27440 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 27228 KB Output is correct
3 Correct 5 ms 27256 KB Output is correct
4 Correct 5 ms 27224 KB Output is correct
5 Correct 6 ms 27228 KB Output is correct
6 Correct 5 ms 27304 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 27260 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 27272 KB Output is correct
13 Correct 5 ms 27228 KB Output is correct
14 Correct 6 ms 27228 KB Output is correct
15 Correct 5 ms 27308 KB Output is correct
16 Correct 5 ms 27228 KB Output is correct
17 Correct 5 ms 27228 KB Output is correct
18 Correct 5 ms 27228 KB Output is correct
19 Correct 5 ms 27228 KB Output is correct
20 Correct 5 ms 27264 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 27224 KB Output is correct
24 Correct 5 ms 27260 KB Output is correct
25 Correct 5 ms 27228 KB Output is correct
26 Correct 5 ms 27228 KB Output is correct
27 Correct 6 ms 27228 KB Output is correct
28 Incorrect 6 ms 27228 KB Output isn't correct
29 Halted 0 ms 0 KB -