Submission #590735

#	Time	Username	Problem	Language	Result	Execution time	Memory
590735		UncoolAnon	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	9037 ms	2260 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());
	vector<int> ft(cnt+5); 
	function<void(int,int)> update=[&](int index,int value){
		for(;index<ft.size();index+=(index&(-index)))
			ft[index]+=value;  
		return ; 
	}; 
	function<int(int)> query=[&](int index){
		int answer=0; 
		for(;index>0;index-=(index&(-index))) answer+=ft[index]; 
		return answer; 
	}; 	
	for(int i=0;i<x.size();i++){
		a[x[i]]=v[i]; 
		int cnt=0; 
		for(int j=0;j<a.size();j++){
			answer[i]=max(answer[i],j-query(a[j]));  
			update(a[j],1); 
		}
		for(int j=0;j<a.size();j++) update(a[j],-1); 
	}
	return answer; 
}

Compilation message (stderr)

bubblesort2.cpp: In lambda function:
bubblesort2.cpp:21:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(;index<ft.size();index+=(index&(-index)))
      |        ~~~~~^~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |  for(int i=0;i<x.size();i++){
      |              ~^~~~~~~~~
bubblesort2.cpp:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(int j=0;j<a.size();j++){
      |               ~^~~~~~~~~
bubblesort2.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(int j=0;j<a.size();j++) update(a[j],-1);
      |               ~^~~~~~~~~
bubblesort2.cpp:32:7: warning: unused variable 'cnt' [-Wunused-variable]
   32 |   int cnt=0;
      |       ^~~

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