Submission #886491

#	Time	Username	Problem	Language	Result	Execution time	Memory
886491		boris_mihov	Money (IZhO17_money)	C++17	100 / 100	443 ms	23380 KiB

money

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <bitset>
#include <vector>
#include <stack>

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

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

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

        return res;
    }

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

        return pos + 1;
    }
};

int a[MAXN];
int dp[MAXN];
int prefix[MAXN];
bool endHere[MAXN];
std::stack <int> st;
Fenwick tree;

void solve()
{
    for (int i = 1 ; i <= n ; ++i)
    {
        prefix[i] = prefix[i - 1] + (a[i - 1] > a[i]);
        tree.update(a[i], 1);
    }

    for (int i = n ; i >= 1 ; --i)
    {
        tree.update(a[i], -1);
        int allowedTo = tree.findKth(tree.query(a[i]) + 1);
        int l = i, r = n + 1, mid;
        while (l < r - 1)
        {
            mid = (l + r) / 2;
            if (a[mid] <= allowedTo && prefix[mid] - prefix[i] == 0)
            {
                l = mid;
            } else
            {
                r = mid;
            }
        }

        int min = n;
        for (int idx = i ; idx <= l ; ++idx)
        {
            min = std::min(min, dp[idx + 1]);
        }

        dp[i] = min + 1;
    }

    std::cout << dp[1] << '\n';
}

void input()
{
    std::cin >> n;
    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;
}

/*
8
7 6 8 1 5 2 4 3
7 | 5 7 | 1 4 | 1 2 | 1

1 | 1 |1 2| 4 | 5 7 | 7

7 5 7 1 4 1 2 1

5
7 | 5 7 | 1 5 2 4 3
*/

• Subtask 1: 9 / 9
• Subtask 2: 16 / 16
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55