Submission #66799

#	Time	Username	Problem	Language	Result	Execution time	Memory
66799		Diuven	Bubble Sort 2 (JOI18_bubblesort2)	C++11	100 / 100	2089 ms	80756 KiB

bubblesort2

#include "bubblesort2.h"
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int inf=2e9;

int n, q, B[1<<20], lim;

vector<pii> comp;

struct node{
	int mx, lz, cnt;
} tree[1<<21];

void lazy(int v, int val){
	tree[v].mx-=val, tree[v].cnt+=val, tree[v].lz+=val;
}
void busy(int v, int s, int e){
	int &z=tree[v].lz;
	if(s!=e){
		lazy(v*2, z);
		lazy(v*2+1,z);
	}
	z=0;
}
void del(int v, int s, int e, int pos){
	busy(v,s,e);
	node &nd=tree[v];
	if(s==e){
		nd.mx=-nd.cnt;
		return;
	}
	int m=(s+e)/2;
	if(pos<=m){
		lazy(v*2+1,-1);
		del(v*2,s,m,pos);
	}
	else{
		del(v*2+1,m+1,e,pos);
	}
	nd.mx=max(tree[v*2].mx, tree[v*2+1].mx);
}
void del(int pos){
	del(1,1,lim,pos);
}
void add(int v, int s, int e, int pos, int idx){
	busy(v,s,e);
	node &nd=tree[v];
	if(s==e){
		nd.mx=idx-nd.cnt;
		return;
	}
	int m=(s+e)/2;
	if(pos<=m){
		lazy(v*2+1,1);
		add(v*2,s,m,pos,idx);
	}
	else{
		add(v*2+1,m+1,e,pos,idx);
	}
	nd.mx=max(tree[v*2].mx, tree[v*2+1].mx);
}
void add(int pos, int idx){
	add(1,1,lim,pos,idx);
}
int mx(){
	return tree[1].mx;
}

void debug(int v=1, int s=1, int e=lim){
	busy(v,s,e);
	node &nd=tree[v];
	if(s==e){ cout<<s<<": "<<nd.mx<<' '<<nd.cnt<<'\n'; return; }
	int m=(s+e)/2;
	debug(v*2,s,m);
	debug(v*2+1,m+1,e);
}

int resp(int x, int pos){
	return lower_bound(comp.begin(), comp.end(), pii({x,pos}))-comp.begin()+1;
}

vi countScans(vi A, vi X, vi V){

	vi ans;

	n=A.size(), q=X.size();

	for(int i=0; i<n; i++) comp.push_back({A[i], i});
	for(int i=0; i<q; i++) comp.push_back({V[i], X[i]});

	sort(comp.begin(), comp.end());
	lim=unique(comp.begin(), comp.end())-comp.begin();
	comp.resize(lim);

	for(int i=0; i<n; i++){
		int val=resp(A[i], i);
		B[i]=val;
		add(val, i);
	}

	for(int ii=0; ii<q; ii++){
		int val=resp(V[ii], X[ii]), idx=X[ii];
		del(B[idx]);
		B[idx]=val;
		add(val, idx);
		ans.push_back(mx());
	}

	return ans;
}

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