Submission #58283

#	Time	Username	Problem	Language	Result	Execution time	Memory
58283		Kmcode	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	4601 ms	57352 KiB

bubblesort2

//#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;


vector<pair<int,int> > lis;

long long int seg[1<<21];
long long int lazy[1<<21];

void upd(int b){
	seg[b]+=lazy[b];
	if(b*2+2<(1<<21)){
		lazy[b*2+1]+=lazy[b];
		lazy[b*2+2]+=lazy[b];
	}
	lazy[b]=0;
}
inline void add(int b,int l,int r,int ll,int rr,long long int x){
	upd(b);
	if(r<=ll||rr<=l){
		return;
	}
	if(ll<=l&&r<=rr){
			lazy[b]+=x;
			upd(b);
		return;
	}
	add(b*2+1,l,(l+r)>>1,ll,rr,x);
	add(b*2+2,(l+r)>>1,r,ll,rr,x);
	seg[b]=max(seg[b*2+1],seg[b*2+2]);
}
int get_id(int pos,int val){
	return lower_bound(lis.begin(),lis.end(),make_pair(val,pos))-lis.begin();
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	for(int i=0;i<A.size();i++){
		lis.push_back(make_pair(A[i],i));
	}
	for(int i=0;i<X.size();i++){
		lis.push_back(make_pair(V[i],X[i]));
	}
	sort(lis.begin(),lis.end());
	lis.erase(unique(lis.begin(),lis.end()),lis.end());
	for(int i=0;i<A.size();i++){
		int z=get_id(i,A[i]);
		add(0,0,lis.size(),z,z+1,i);
		add(0,0,lis.size(),lower_bound(lis.begin(),lis.end(),make_pair(A[i],-1))-lis.begin(),lis.size(),-1);
	}
	vector<int> res;
	for(int ii=0;ii<X.size();ii++){
		int i=X[ii];
		int z=get_id(i,A[i]);
		add(0,0,lis.size(),z,z+1,-i);
		add(0,0,lis.size(),lower_bound(lis.begin(),lis.end(),make_pair(A[i],-1))-lis.begin(),lis.size(),1);
		A[i]=V[ii];
		z=get_id(i,A[i]);
		add(0,0,lis.size(),z,z+1,i);
		add(0,0,lis.size(),lower_bound(lis.begin(),lis.end(),make_pair(A[i],-1))-lis.begin(),lis.size(),-1);
		upd(0);
		res.push_back(seg[0]+1);
	}
	return res;
}
 

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:51:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int ii=0;ii<X.size();ii++){
               ~~^~~~~~~~~

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