Submission #284034

#	Time	Username	Problem	Language	Result	Execution time	Memory
284034		AMnu	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	3382 ms	130936 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;
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;
		balance();
		
		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 del(pii x) {
	int y=lower_bound(S.begin(),S.end(),x)-S.begin();
	data.set(y,-INF,0);
	data.update(y+1,1);
}

void add(pii x) {
	int y=lower_bound(S.begin(),S.end(),x)-S.begin();
	data.set(y,x.i2-data.query(y-1),1);
	data.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());
	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]=data.val;
	}
	
	return H;
}

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