Submission #321593

#	Time	Username	Problem	Language	Result	Execution time	Memory
321593		CaroLinda	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	5015 ms	110408 KiB

bubblesort2

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

#define sz(x) (int)(x.size() )
#define all(x) x.begin(),x.end()

const int MAX = 1e6+10 ;
const int inf = 1e8+10 ;

using namespace std ;

int Key ;

struct Tree
{
	
	int tree[MAX*4] ;
	int lz[MAX*4] ;

	int m(int l, int r ) { return (l+r)>>1 ; }

	void refresh(int pos, int l, int r )
	{
		tree[pos] += lz[pos] ;

		if( l == r ) return (void)(lz[pos] = 0 ) ;

		lz[pos<<1] += lz[pos] ;
		lz[pos<<1|1] += lz[pos] ;

		lz[pos] = 0 ;

	}

	void updInterval(int pos, int l,int r, int beg, int en, int val )
	{
		refresh(pos,l,r) ;

		if( l > en || r < beg ) return ;
		if( l >= beg && r <= en )
		{
			lz[pos] += val ;
			refresh(pos,l,r) ;
			return ;
		}

		updInterval(pos<<1 , l, m(l,r) , beg, en, val ) ;
		updInterval(pos<<1|1 , m(l,r)+1, r, beg, en, val ) ;

		tree[pos] = max(tree[pos<<1], tree[pos<<1|1] ) ;

	}

	void updPoint(int pos, int l ,int r, int idx, int val )
	{
		refresh(pos,l,r) ;

		if( l > idx || r < idx ) return ;
		if( l == r ) return (void)(tree[pos] = val) ;

		updPoint(pos<<1 , l ,m(l,r), idx, val ) ;
		updPoint(pos<<1|1 , m(l,r)+1, r, idx, val ) ;	

		tree[pos] = max(tree[pos<<1] , tree[pos<<1|1] ) ;

	}

	int getMax() { refresh(1,0,1) ; return tree[1] ; }

} seg ;

struct Bit
{
	
	int bit[MAX] ;

	void upd(int pos, int x ) { for(; pos < MAX ; pos += pos & -pos ) bit[pos] += x ; }
	int qry(int pos )
	{
		int tot = 0 ;
		for(; pos > 0 ; pos -= pos & -pos ) tot += bit[pos] ;
		return tot ;
	}

} bit ;

vector<int> countScans( vector<int> A, vector<int> X, vector<int> V)
{

	int n = sz(A) ;
	int q = sz(V) ;

	map< pair<int,int> , int > compression ;

	for(int i = 0 ; i < n ; i++ ) compression[ make_pair(A[i],i) ] = 0 ;
	for(int i = 0 ; i < q ; i++ ) compression[ make_pair(V[i], X[i]) ] = 0 ;

	for(auto &e : compression ) e.second = ++Key ;

	for(int i = 0 ; i < n ; i++ ) A[i] = compression[ make_pair(A[i], i) ] ;
	for(int i = 0 ; i < q ; i++ ) V[i] = compression[ make_pair(V[i] , X[i] ) ] ;

	seg.updInterval(1,1,Key, 1,Key, -inf ) ;

	for(int i = 0 ; i < n ; i++ )	bit.upd(A[i], 1) ;
	for(int i = 0 ; i < n ; i++ ) seg.updPoint(1,1, Key,A[i],  i-bit.qry(A[i]-1) ) ;

	vector<int> ans ;

	for(int i = 0 ; i < q ; i++ )
	{
		bit.upd( A[ X[i] ] , -1 ) ;
		bit.upd( V[i] , 1 ) ;

		seg.updInterval( 1 , 1 , Key , A[ X[i] ] + 1 , Key , 1 ) ;
		seg.updInterval(1 , 1 , Key , V[i] + 1 , Key , -1 ) ;

		seg.updPoint(1 , 1  , Key , A[ X[i] ] , -inf ) ;
		seg.updPoint(1,1,Key, V[i] , X[i] - bit.qry(V[i] - 1) ) ;

		A[X[i]] = V[i] ;

		ans.push_back( seg.getMax() ) ;	
	
	}

	return ans ;

}

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