Submission #852221

#	Time	Username	Problem	Language	Result	Execution time	Memory
852221		LucaIlie	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	33 ms	68176 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>


using namespace __gnu_pbds;
using namespace std;

const int MAX_N = 5e5;
const int MAX_AINT = 2 * MAX_N;
const int INF = 1e9;

struct AINT {
    struct info {
        int minn, maxx;

        info operator + ( info x ) {
            return { min( minn, x.minn ), max( maxx, x.maxx ) };
        }
    };

    info aint[4 * MAX_AINT];
    set<int> poses[MAX_AINT + 1];

    void update( int v, int l, int r, int pos, int val ) {
        if ( l > pos || r < pos )
            return;

        if ( l == r ) {
            if ( val >= 0 )
                poses[l].insert( val );
            else
                poses[l].erase( -(val - 1) );

            aint[v] = (poses[l].empty() ? info{ INF, -INF } : info{ *poses[l].begin(), *poses[l].rbegin() } );
            return;
        }

        int mid = (l + r) / 2;
        update( v * 2 + 1, l, mid, pos, val );
        update( v * 2 + 2, mid + 1, r, pos, val );
        aint[v] = aint[v * 2 + 1] + aint[v * 2 + 2];
    }

    info query( int v, int l, int r, int lq, int rq ) {
        if ( lq > rq )
            return { INF, -INF };

        if ( l > rq || r < lq )
            return { INF, -INF };

        if ( lq <= l && r <= rq )
            return aint[v];

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

struct per {
    int i, j;

    bool operator < ( const per &x ) const {
        return abs( i - j ) > abs( x.i - x.j );
    }
};

int leftPair[MAX_N + 1], rightPair[MAX_N + 1];
vector<int> pairs[MAX_N + 1];
map<int, int> mp;
set<per> cand;

vector<int> countScans( vector<int> v, vector<int> pos, vector<int> val ){
    int n = v.size();
    int q = pos.size();
    vector<int> ans( q );

    for ( int i = 0; i < n; i++ )
        mp[v[i]] = 1;
    for ( int i = 0; i < q; i++ )
        mp[val[i]] = 1;
    int valmax = 0;
    for ( auto x: mp )
        mp[x.first] = ++valmax;
    for ( int i = 0; i < n; i++ )
        v[i] = mp[v[i]];
    for ( int i = 0; i < q; i++ )
        val[i] = mp[val[i]];

    for ( int i = 0; i < n; i++ ) {
        aint.update( 0, 1, valmax, v[i], i );

        int pl = aint.query( 0, 1, valmax, v[i] + 1, valmax ).minn;
        leftPair[i] = -1;
        if ( 0 <= pl && pl < i ) {
            leftPair[i] = pl;
            pairs[leftPair[i]].push_back( i );
            cand.insert( { leftPair[i], i } );
        }

        int pr = aint.query( 0, 1, valmax, 1, v[i] - 1 ).maxx;
        rightPair[i] = -1;
        if ( i < pr && pr < n ) {
            rightPair[i] = pr;
            pairs[rightPair[i]].push_back( i );
            cand.insert( { i, rightPair[i] } );
        }
    }

    for ( int l = 0; l < q; l++ ) {
        int i = pos[l];

        for ( int j: pairs[i] )
            cand.erase( { min( i, j ), max( i, j ) } );
        if ( leftPair[i] != -1 )
            cand.erase( { leftPair[i], i } );
        if ( rightPair[i] != -1 )
            cand.erase( { i, rightPair[i] } );

        aint.update( 0, 1, valmax, v[i], -(i + 1) );
        v[i] = val[l];
        aint.update( 0, 1, valmax, v[i], i );

        int pl = aint.query( 0, 1, valmax, v[i] + 1, valmax ).minn;
        leftPair[i] = -1;
        if ( 0 <= pl && pl < i ) {
            leftPair[i] = pl;
            pairs[leftPair[i]].push_back( i );
            cand.insert( { leftPair[i], i } );
        }

        int pr = aint.query( 0, 1, valmax, 1, v[i] - 1 ).maxx;
        rightPair[i] = -1;
        if ( i < pr && pr < n ) {
            rightPair[i] = pr;
            pairs[rightPair[i]].push_back( i );
            cand.insert( { i, rightPair[i] } );
        }

        ans[l] = (cand.empty() ? 0 : cand.begin()->j - cand.begin()->i);
    }

    return ans;
}

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