Submission #64628

#	Time	Username	Problem	Language	Result	Execution time	Memory
64628		zscoder	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	7913 ms	339216 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const int INF = int(1e9);

struct node
{
	int mn,lazy;
};

node st[4222222];

void push(int id, int l, int r)
{
	if(st[id].lazy!=0)
	{
		st[id].mn+=st[id].lazy;
		if(r-l>=2)
		{
			st[id*2].lazy+=st[id].lazy;
			st[id*2+1].lazy+=st[id].lazy;
		}
		st[id].lazy=0;
	}
}

void combine(int id)
{
	st[id].mn=min(st[id*2].mn,st[id*2+1].mn);
}

void build(int id, int l, int r)
{
	if(r-l<2)
	{
		st[id].lazy=0;
		st[id].mn=INF;
		return ;
	}	
	int mid=(l+r)>>1;
	build(id*2,l,mid); build(id*2+1,mid,r);
	combine(id);
}

void add(int id, int l, int r, int ql, int qr, int v)
{
	push(id,l,r);
	if(ql>=r||l>=qr) return ;
	if(ql<=l&&r<=qr)
	{
		st[id].lazy+=v;
		push(id,l,r);
		return ;
	}
	int mid=(l+r)>>1;
	add(id*2,l,mid,ql,qr,v); add(id*2+1,mid,r,ql,qr,v);
	combine(id);
}

void update(int id, int l, int r, int pos, int v)
{
	push(id,l,r);
	if(pos>=r||pos<l) return ;
	if(r-l<2)
	{
		st[id].lazy=0; st[id].mn=v;
		return ;
	}
	int mid=(l+r)>>1;
	update(id*2,l,mid,pos,v); update(id*2+1,mid,r,pos,v);
	combine(id);
}

int query(int id, int l, int r, int ql, int qr)
{
	push(id,l,r);
	if(ql>=r||l>=qr) return INF;
	if(ql<=l&&r<=qr) return st[id].mn;
	int mid=(l+r)>>1;
	return min(query(id*2,l,mid,ql,qr),query(id*2+1,mid,r,ql,qr));
}

pbds T;
int ma[511111];
int maq[511111];

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V)
{
	int Q=X.size();
	std::vector<int> answer(Q);
	int n = A.size(); T.clear();
	int timer=0;
	for(int i=0;i<n;i++) T.insert(mp(A[i],++timer));
	vector<pair<int,ii> > vec;
	for(int i=0;i<n;i++) vec.pb(mp(A[i],mp(i,-1)));
	for(int i=0;i<Q;i++) vec.pb(mp(V[i],mp(X[i],i)));
	sort(vec.begin(),vec.end());
	int N = n+Q;
	for(int i=0;i<N;i++)
	{
		if(vec[i].se.se==-1)
		{
			ma[vec[i].se.fi] = i;
		}
	}
	for(int i=0;i<N;i++)
	{
		if(vec[i].se.se>=0)
		{
			maq[vec[i].se.se] = i;
		}
	}
	for(int i=0;i<n;i++)
	{
		update(1,0,N,ma[i],-(i+1)+T.order_of_key(mp(A[i]+1,-2)));
		//cerr<<"P : "<<i<<' '<<(i+1)-T.order_of_key(mp(A[i]+1,-2))<<'\n';
	}
	for(int i=0;i<Q;i++) 
	{
		auto it = T.lower_bound(mp(A[X[i]],-1)); T.erase(it); T.insert(mp(V[i],++timer));
		update(1,0,N,ma[X[i]],INF);
		ma[X[i]] = maq[i];
		//remove A[X[i]] from memories
		//add V[i] to memories
		int lb = lower_bound(vec.begin(),vec.end(),mp(A[X[i]],mp(-2,-2))) - vec.begin();
		add(1,0,N,lb,N,-1);
		lb = lower_bound(vec.begin(),vec.end(),mp(V[i],mp(-2,-2))) - vec.begin();
		add(1,0,N,lb,N,1);
		update(1,0,N,ma[X[i]],-(X[i]+1)+int(T.order_of_key(mp(V[i]+1,-2))));
		//cerr<<"SPECIAL : "<<-(X[i]+1)+int(T.order_of_key(mp(V[i]+1,-2)))<<'\n';
		answer[i] = -query(1,0,N,0,N);
		A[X[i]] = V[i];
	}
	return answer;
}

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