Submission #408633

#	Time	Username	Problem	Language	Result	Execution time	Memory
408633		AmineWeslati	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	237 ms	104796 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;

typedef long long ll;
typedef vector<int>vi;
#define pb push_back
#define sz(v) (int)v.size()
#define all(x) begin(x),end(x)

#define FOR(i,a,b) for(int i=a; i<b; i++)
#define ROF(i,a,b) for(int i=b-1; i>=a; i--)

//--------------------------------------------//

int N,Q;
vi a; 

const int MX=5e5+10;
set<int>t[MX*4];

void build(int pos=1, int tl=0, int tr=N-1){
	if(tl==tr){
		t[pos].insert(a[tl]);
		return; 
	}

	int tm=(tl+tr)/2;
	build(pos*2,tl,tm);
	build(pos*2+1,tm+1,tr);

	for(int x: t[pos*2]) t[pos].insert(x);
	for(int x: t[pos*2+1]) t[pos].insert(x);
}

void upd(int idx, int v, int vo, int pos=1, int tl=0, int tr=N-1){
	t[pos].erase(vo); 
	t[pos].insert(v); 

	if(tl==tr)
		return; 

	int tm=(tl+tr)/2;
	if(idx<=tl) upd(idx,v,vo,pos*2,tl,tm);
	else upd(idx,v,vo,pos*2+1,tm+1,tr);
}

int get(int ty, int l, int r, int v, int pos=1, int tl=0, int tr=N-1){
	if(l>r) return 0;
	if(tl==l && tr==r){
		int cnt=0;
		if(ty){
			for(int x: t[pos]){
				if(x<v) cnt++;
				else break;
			}
		}
		else{
			for(int x: t[pos]){
				if(x>v) cnt++;
			}
		}
		return cnt; 
	}

	int tm=(tl+tr)/2;
	return get(ty,l,min(r,tm),v,pos*2,tl,tm) 
		+ get(ty,max(l,tm+1),r,v,pos*2+1,tm+1,tr);
}

vi countScans(vi A,vi X,vi V){
	N=sz(A); Q=sz(X);
	a.assign(all(A));

	build();
	int ans=0;
	FOR(i,0,N){
		ans+=get(0,0,i,a[i]);
		ans+=get(1,i,N-1,a[i]);
	}

	vi res(Q);
	FOR(i,0,Q){
		int idx=X[i],v=V[i];

		ans-=get(0,0,idx,a[idx]);
		ans-=get(1,idx,N-1,a[idx]);

		upd(idx,v,a[idx]);

		ans+=get(0,0,idx,a[idx]);
		ans+=get(1,idx,N-1,a[idx]);

		res[i]=ans; 
	}
	return res;
}

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