Submission #590892

#	Time	Username	Problem	Language	Result	Execution time	Memory
590892		UncoolAnon	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	44 ms	4584 KiB

bubblesort2

#include <bits/stdc++.h> 
#define pii pair<int,int> 
#define F first 
#define S second 
#define mp make_pair 
#define endl '\n'
using namespace std; 
const int inf=1e9,N=2e5+5,md=1e9+7; 
vector<int> countScans(vector<int> a ,vector<int> x , vector<int> v){
	set<int> c; 
	map<int,int> m; 
	for(int&x:a) c.insert(x); 
	for(int&x:v) c.insert(x); 
	int cnt=1; 
	for(int x:c) m[x]=cnt++;
	for(int&x:a) x=m[x];  
	for(int&x:v) x=m[x]; 
	vector<int> answer(x.size()),sg((cnt+5)*4); 
	vector<set<int>> cc(cnt+5); 
	vector<int> lz=sg; 
	for(int&x:sg) x=-inf; 
	for(set<int>&x:cc) x.insert(-inf); 
	function<void(int,int,int)> push=[&](int i,int l,int r){
		sg[i]+=lz[i]; 
		if(l!=r){
			lz[i*2]+=lz[i]; 
			lz[i*2+1]+=lz[i]; 
		}
		lz[i]=0; 
		return; 
	}; 
	function<void(int,int,int,int,int)> update=[&](int i,int l,int r,int index,int v){
		push(i,l,r); 
		if(index<l||r<index) return ; 
		if(l==r){
			sg[i]-=*(--cc[l].end()); 
			if(v<0) cc[l].erase(-v-1); 
			else cc[l].insert(v-1); 
			sg[i]+=*(--cc[l].end()); 
			return ; 
		}
		update(i*2,l,(r+l)/2,index,v); 
		update(i*2+1,(r+l)/2+1,r,index,v); 
		sg[i]=max(sg[i*2],sg[i*2+1]); 
		return ; 
	}; 
	function<void(int,int,int,int,int,int)> range=[&](int i,int l,int r,int ql,int qr,int v){
		push(i,l,r); 
		if(qr<l||r<ql) return;
		if(ql<=l&&r<=qr){
			lz[i]+=v; 
			push(i,l,r); 
			return; 
		}
		range(i*2,l,(r+l)/2,ql,qr,v); 
		range(i*2+1,(r+l)/2+1,r,ql,qr,v); 
		sg[i]=max(sg[i*2],sg[i*2+1]); 
		return; 
	};
	for(int i=0;i<a.size();i++){ 
		update(1,0,cnt,a[i],i+1);  
		range(1,0,cnt,a[i]+1,cnt,-1); 
	}
	for(int i=0;i<x.size();i++){
		update(1,0,cnt,a[x[i]],-(x[i]+1)); 
		range(1,0,cnt,a[x[i]]+1,cnt,1); 
		a[x[i]]=v[i]; 
		update(1,0,cnt,a[x[i]],x[i]+1); 
		range(1,0,cnt,a[x[i]]+1,cnt,-1); 
		push(1,0,cnt);
		answer[i]=sg[1]; 
	}
	return answer; 
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i=0;i<a.size();i++){
      |              ~^~~~~~~~~
bubblesort2.cpp:64:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i=0;i<x.size();i++){
      |              ~^~~~~~~~~

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