Submission #97800

#	Time	Username	Problem	Language	Result	Execution time	Memory
97800		scanhex	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	15 ms	2048 KiB

bubblesort2

#include<bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

const int N=500500;
int a[N];
int n;
set<pair<int,int>>all;
int sz1=100;
int sz2=0;

int memos[N];

void reb_int(){
}

int cnt=0;

void upd(int i,int coef){
	auto p=make_pair(a[i],i);
	if(coef==-1)
		all.erase(p);
	if(coef==1)
		all.insert(p);
	vector<int>kek;
	auto it=all.begin();
	for(int i=0;i<sz2;++i,++it){
		kek.push_back(it->second);
	}
	for(int i=0;i<sz1;++i)kek.push_back(n-i-1);
	sort(kek.begin(),kek.end());
	kek.erase(unique(kek.begin(),kek.end()),kek.end());
	for(int x:kek){
		if(i<x&&a[i]>a[x])memos[x]+=coef;
	}
	/*
	if(++cnt==1000){
		reb_int();
	}
	*/
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> x,std::vector<int> v){
	sz1=min(sz1,n);
	sz2=min(sz2,n);
	n=A.size();
	copy(A.begin(),A.end(),a);
	for(int i=0;i<n;++i)upd(i,1);
	int q=x.size();
	vector<int>answer(q);
	for(int i=0;i<q;++i){
		upd(x[i],-1);
		a[x[i]]=v[i];
		upd(x[i],1);
		for(int j=0;j<sz1;++j){
			answer[i]=max(answer[i],memos[j]);
		}
	}
	return answer;
}

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