oj.uz

Submission #522340

# Submission time Handle Problem Language Result Execution time Memory
522340 2022-02-04T16:02:43 Z LucaIlie Money (IZhO17_money) C++17
0 / 100
 1 ms 332 KB 
#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;
        frecv.update( v[i], 1 );
        while ( j < n && v[j - 1] <= v[j] && frecv.query( v[j] ) - frecv.query( v[i] - 1 ) == j - i ) {
            frecv.update( v[j], 1 );
            j++;
        }
        i = j;
        subSegm++;
    }

    cout << subSegm;

    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -