Submission #1295647

#	Time	Username	Problem	Language	Result	Execution time	Memory
1295647		k12_khoi	Money (IZhO17_money)	C++17	0 / 100	1 ms	576 KiB

money

#include <bits/stdc++.h>
using namespace std;

const int N=1e6+5;

int n,mx_bit,last,res;
int a[N],bit[N];

void fenwick_update(int u)
{
    for (int idx=u;idx<=n;idx+=idx&-idx)
    bit[idx]++;
}

int fenwick_get(int u)
{
    int ans=0;

    for (int idx=u;idx>0;idx-=idx&-idx)
    ans+=bit[idx];

    return ans;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    mx_bit=1e6;

    cin >> n;
    last=1;
    res=1;
    for (int i=1;i<=n;i++)
    {
        cin >> a[i];

        if (i!=1 and (a[i-1]>a[i] or fenwick_get(a[i]-1)-fenwick_get(a[i-1])>0))
        {
            res++;
            for (int j=last;j<i;j++)
            fenwick_update(a[j]);

            last=i;
        }
    }

    cout << res;
}

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