Submission #522349

#	Time	Username	Problem	Language	Result	Execution time	Memory
522349		LucaIlie	Money (IZhO17_money)	C++17	100 / 100	356 ms	14984 KiB

money

#include <iostream>

#define MAX_N 1000000
#define MAX_A 1000000

using namespace std;

int v[MAX_N];

struct AIB {
    int aib[MAX_A + 1];

    void update( int i, int x ) {
        while ( i <= MAX_A ) {
            aib[i] += x;
            i += (i & -i);
        }
    }

    int query( int i ) {
        int s;

        s = 0;
        while ( i > 0 ) {
            s += aib[i];
            i -= (i & -i);
        }

        return s;
    }
};

AIB frecv;

int main() {
    int n, subSegm, i, j;

    cin >> n;
    for ( i = 0; i < n; i++ )
        cin >> v[i];

    subSegm = 0;
    i = 0;
    while ( i < n ) {
        j = i + 1;
        while ( j < n && v[j - 1] <= v[j] && frecv.query( v[j] - 1 ) - frecv.query( v[i] ) <= 0 )
            j++;

        for ( ; i < j; i++ )
            frecv.update( v[i], 1 );
        subSegm++;
    }

    cout << subSegm;

    return 0;
}

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