Submission #284031

#	Time	Username	Problem	Language	Result	Execution time	Memory
284031		AMnu	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	9005 ms	3328 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#define pii pair<int,int>
#define i1 first
#define i2 second
using namespace std;

const int INF=1e6+5;

int N, Q;
int T[INF];
int C[INF];
vector<int> H;
vector<pii> S;

void build(int x,int y) {
	for (int i=x;i<=y;i++) {
		T[i]=-INF;
		C[i]=0;
	}
}

void update(int x,int y) {
	for (int i=x;i<N+Q;i++) {
		T[i]+=y;
	}
}

int query(int x) {
	int ret=0;
	
	for (int i=0;i<=x;i++) {
		ret+=C[i];
	}
	
	return ret;
}

int ans() {
	int ret=-INF;
	
	for (int i=0;i<N+Q;i++) {
		ret=max(ret,T[i]);
	}
	
	return ret;
}

void del(pii x) {
	int y=lower_bound(S.begin(),S.end(),x)-S.begin();
	T[y]=-INF;
	C[y]=0;
	update(y+1,1);
}

void add(pii x) {
	int y=lower_bound(S.begin(),S.end(),x)-S.begin();
	T[y]=x.i2-query(y-1);
	C[y]=1;
	update(y+1,-1);
}

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	N=A.size();
	Q=X.size();
	H=vector<int>(Q);
	S=vector<pii>(N+Q);
	
	for (int i=0;i<N;i++) {
		S[i]={A[i],i};
	}
	
	for (int i=0;i<Q;i++) {
		S[i+N]={V[i],X[i]};
	}
	
	sort(S.begin(),S.end());
	build(0,N+Q-1);
	
	for (int i=0;i<N;i++) {
		add({A[i],i});
	}
	
	for (int i=0;i<Q;i++) {
		del({A[X[i]],X[i]});
		A[X[i]]=V[i];
		add({A[X[i]],X[i]});
		H[i]=ans();
	}
	
	return H;
}

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