Submission #284032

#	Time	Username	Problem	Language	Result	Execution time	Memory
284032		AMnu	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	9102 ms	12280 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];
vector<int> H;
vector<pii> S;

struct segment {
	int L, R;
	int val, cnt, lazy;
	segment *lef, *rig;
	
	void build(int x,int y) {
		L=x;
		R=y;
		val=-INF;
		cnt=0;
		lazy=0;
		
		if (x==y) {
			return;
		}
		
		int T;
		T=(L+R)/2;
		lef=new segment;
		lef->build(L,T);
		rig=new segment;
		rig->build(T+1,R);
		
		return;
	}
	
	void balance() {
		if (!lazy) {
			return;
		}
		
		lef->val+=lazy;
		lef->lazy+=lazy;
		rig->val+=lazy;
		rig->lazy+=lazy;
		lazy=0;
		
		return;
	}
	
	void update(int x,int y) {
		if (R<x) {
			return;
		}
		
		if (L>=x) {
			val+=y;
			lazy+=y;
			return;
		}
		
		balance();
		lef->update(x,y);
		rig->update(x,y);
		val=max(lef->val,rig->val);
		
		return;
	}
	
	int query(int x) {
		if (L>x) {
			return 0;
		}
		
		if (R<=x) {
			return cnt;
		}
		
		return lef->query(x)+rig->query(x);
	}
	
	void set(int x,int y,int z) {
		if (L==R) {
			val=y;
			cnt=z;
			return;
		}
		
		int T;
		T=(L+R)/2;
		
		if (x<=T) {
			lef->set(x,y,z);
		}
		else {
			rig->set(x,y,z);
		}
		
		cnt=lef->cnt+rig->cnt;
		val=max(lef->val,rig->val);
	}
}
data;

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

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

int query(int x) {
	return data.query(x);
}

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;
	data.set(y,0,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);
	data.set(y,0,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);
	data.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