Submission #956275

#	Time	Username	Problem	Language	Result	Execution time	Memory
956275		LucaIlie	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3034 ms	129144 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

struct SegTree {
    int segLeft, segRight;
    vector<int> segTree;
    vector<int> lazy;

    void init( int l, int r  ) {
        segLeft = l;
        segRight = r;

        segTree.resize( 4 * (r - l + 1) );
        lazy.resize( 4 * (r - l + 1) );
    }

    void propag( int v, int l, int r ) {
        segTree[v] += lazy[v];
        if ( l != r ) {
            lazy[v * 2 + 1] += lazy[v];
            lazy[v * 2 + 2] += lazy[v];
        }
        lazy[v] = 0;
    }

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

        if ( lu <= l && r <= ru ) {
            lazy[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] );
    }
    void update( int l, int r, int x ) {
        update( 0, segLeft, segRight, l, r, x );
    }

    int query() {
        return segTree[0];
    }
};

map<long long, int> values;
SegTree inversions;

vector<int> countScans( vector<int> A, vector<int> pos, vector<int> V ){
    int n = A.size(), q = V.size();
    vector<int> ans( q );
    vector<long long> a( n ), val( q );

    for ( int i = 0; i < n; i++ )
        values[(long long)A[i] * n + i] = 1;
    for ( int i = 0; i < q; i++ )
        values[(long long)V[i] * n + pos[i]] = 1;
    int m = 0;
    for ( auto p: values )
        values[p.first] = ++m;
    for ( int i = 0; i < n; i++ )
        a[i] = values[(long long)A[i] * n + i];
    for ( int i = 0; i < q; i++ )
        val[i] = values[(long long)V[i] * n + pos[i]];

    inversions.init( 1, m );
    for ( int i = 0; i < n; i++ ) {
        inversions.update( a[i], a[i], i );
        inversions.update( a[i] + 1, m, -1 );
    }

    for ( int u = 0; u < q; u++ ) {
        int i = pos[u];
        inversions.update( a[i], a[i], -i );
        inversions.update( a[i] + 1, m, 1 );
        a[i] = val[u];
        inversions.update( a[i], a[i], i );
        inversions.update( a[i] + 1, m, -1 );
        ans[u] = inversions.query();
    }

    return ans;
}

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40