oj.uz

Submission #851030

# Submission time Handle Problem Language Result Execution time Memory
851030 2023-09-18T08:45:23 Z LucaIlie Financial Report (JOI21_financial) C++17
19 / 100
 689 ms 31060 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5;
int v[MAX_N], p[MAX_N];

struct SegTree {
    int segTree[4 * MAX_N];
    int lazy[4 * MAX_N];

    void propag( int v, bool leaf ) {
        if ( segTree[v] == 0 )
            return;
        segTree[v] = max( segTree[v], lazy[v] );
        if ( !leaf ) {
            lazy[v * 2 + 1] = max( lazy[v * 2 + 1], lazy[v] );
            lazy[v * 2 + 2] = max( lazy[v * 2 + 2], lazy[v] );
        }
        lazy[v] = 0;
    }

    void updatePos( int v, int l, int r, int pos, int x ) {
        propag( v, (l == r) );

        if ( l > pos || r < pos )
            return;

        if ( l == r ) {
            segTree[v] = max( segTree[v], x );
            return;
        }

        int mid = (l + r) / 2;
        updatePos( v * 2 + 1, l, mid, pos, x );
        updatePos( v * 2 + 2, mid + 1, r, pos, x );
        segTree[v] = max( segTree[v * 2 + 1], segTree[v * 2 + 2] );
    }

    void update( int v, int l, int r, int lu, int ru, int x ) {
        if ( lu > ru )
            return;

        propag( v, (l == r) );

        if ( l > ru || r < lu )
            return;

        if ( lu <= l && r <= ru ) {
            lazy[v] = max( lazy[v], x );
            segTree[v] = max( segTree[v], x );
            propag( v, (l == r) );
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, lu, ru, x );
        update( v * 2 + 2, mid + 1, r, lu, ru, x );
        segTree[v] = max( segTree[v * 2 + 1], segTree[v * 2 + 2] );
    }

    int query( int v, int l, int r, int lq, int rq ) {
        if ( lq > rq )
            return 0;
        propag( v, (l == r));

        if ( l > rq || r < lq )
            return 0;
        if ( lq <= l && r <= rq )
            return segTree[v];

        int mid = (l + r) / 2;
        return max( query( v * 2 + 1, l, mid, lq, rq ), query( v * 2 + 2, mid + 1, r, lq, rq ) );
    }
};

struct DSU {
    int parent[MAX_N + 1], maxx[MAX_N + 1];

    void init() {
        for ( int i = 0; i <= MAX_N; i++ )
            parent[i] = maxx[i] = i;
    }

    int findParent( int u ) {
        if ( parent[u] == u )
            return u;

        parent[u] = findParent( parent[u] );
        return parent[u];
    }

    void join( int u, int v ) {
        u = findParent( u );
        v = findParent( v );

        maxx[u] = max( maxx[u], maxx[v] );
        parent[v] = u;
    }

    int getMax( int u ) {
        return maxx[findParent( u )];
    }
} dsu;

SegTree sir;
set<int> pos;

int main() {
    int n, d;

    cin >> n >> d;
    for ( int i = 1; i <= n; i++ )
        cin >> v[i], p[i] = i;

    sort( p + 1, p + 1 + n, []( int i, int j ) {
        if ( v[i] == v[j] )
            return i > j;
        return v[i] < v[j];
    } );

    dsu.init();
    pos.insert( 0 );
    pos.insert( n + 1 );
    for ( int ii = 1; ii <= n; ii++ ) {
        int i = p[ii];
        int len = sir.query( 0, 1, n, max( 1, i - d ), i - 1 ) + 1;
        sir.updatePos( 0, 1, n, i, len );

        auto ub = pos.upper_bound( i );
        auto lb = pos.lower_bound( i );
        lb--;

        if ( *ub <= n && *ub - i <= d )
            dsu.join( i, *ub );
        if ( *lb >= 1 && i - *ub <= d )
            dsu.join( i, *lb );

        sir.update( 0, 1, n, i + 1, dsu.getMax( i ), len );
        pos.insert( i );
    }

    cout << sir.query( 0, 1, n, n, n );

    return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 2 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Correct 1 ms 4440 KB Output is correct
22 Correct 1 ms 4440 KB Output is correct
23 Correct 1 ms 4440 KB Output is correct
24 Correct 1 ms 4440 KB Output is correct
25 Correct 1 ms 4440 KB Output is correct
26 Correct 1 ms 4440 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 2 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Correct 1 ms 4440 KB Output is correct
22 Correct 1 ms 4440 KB Output is correct
23 Correct 1 ms 4440 KB Output is correct
24 Correct 1 ms 4440 KB Output is correct
25 Correct 1 ms 4440 KB Output is correct
26 Correct 1 ms 4440 KB Output is correct
27 Incorrect 1 ms 4440 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 2 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Correct 1 ms 4440 KB Output is correct
22 Correct 1 ms 4440 KB Output is correct
23 Correct 1 ms 4440 KB Output is correct
24 Correct 1 ms 4440 KB Output is correct
25 Correct 1 ms 4440 KB Output is correct
26 Correct 1 ms 4440 KB Output is correct
27 Incorrect 1 ms 4440 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 27988 KB Output is correct
2 Correct 391 ms 30544 KB Output is correct
3 Incorrect 530 ms 31060 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 28160 KB Output is correct
2 Correct 507 ms 30796 KB Output is correct
3 Correct 604 ms 30800 KB Output is correct
4 Correct 681 ms 30800 KB Output is correct
5 Correct 550 ms 30824 KB Output is correct
6 Correct 622 ms 30800 KB Output is correct
7 Correct 288 ms 30852 KB Output is correct
8 Correct 364 ms 30828 KB Output is correct
9 Correct 355 ms 30544 KB Output is correct
10 Correct 506 ms 30744 KB Output is correct
11 Correct 689 ms 31012 KB Output is correct
12 Correct 498 ms 30800 KB Output is correct

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4440 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4440 KB Output is correct
9 Correct 2 ms 4440 KB Output is correct
10 Correct 1 ms 4440 KB Output is correct
11 Correct 1 ms 4444 KB Output is correct
12 Correct 1 ms 4440 KB Output is correct
13 Correct 1 ms 4440 KB Output is correct
14 Correct 1 ms 4440 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4440 KB Output is correct
17 Correct 1 ms 4440 KB Output is correct
18 Correct 1 ms 4440 KB Output is correct
19 Correct 1 ms 4444 KB Output is correct
20 Correct 1 ms 4440 KB Output is correct
21 Correct 1 ms 4440 KB Output is correct
22 Correct 1 ms 4440 KB Output is correct
23 Correct 1 ms 4440 KB Output is correct
24 Correct 1 ms 4440 KB Output is correct
25 Correct 1 ms 4440 KB Output is correct
26 Correct 1 ms 4440 KB Output is correct
27 Incorrect 1 ms 4440 KB Output isn't correct
28 Halted 0 ms 0 KB -