Submission #162199

#	Time	Username	Problem	Language	Result	Execution time	Memory
162199		mhy908	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	191 ms	1024 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
const LL llinf=987654321987654321;
const int inf=987654321;

int n, q, sz;
int arr[500010];
vector<int> bucket[1000];
void makebucket(){
	sz=sqrt(n);
	for(int i=1; i<=n; i++){
		bucket[(i-1)/sz].pb(arr[i]);
	}
	for(int i=0; i<=n/sz; i++){
		sort(all(bucket[i]));
	}
}
void update(int pos, int val) {
	auto it=lower_bound(all(bucket[(pos-1)/sz]), arr[pos]);
	arr[pos]=val;
	*it=val;
	sort(all(bucket[(pos-1)/sz]));
}
void print()
{
    for(int i=0; bucket[i].size(); i++){
        for(int j=0; j<bucket[i].size(); j++)printf("%d ", bucket[i][j]);
        printf("/ ");
    }
}
int query(int lo, int hi, int k){
	int ret=0;
	while((lo+sz-1)%sz&&lo<=hi){
		if(arr[lo++]>k){
			++ret;
		}
	}
	while(hi%sz&&lo<=hi){
		if(arr[hi--]>k){
			++ret;
		}
	}
	while(lo<=hi){
	    auto it2=upper_bound(all(bucket[(lo-1)/sz]), k);
		ret+=bucket[(lo-1)/sz].end()-it2;
		lo+=sz;
	}
	return ret;
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	n=A.size(), q=X.size();
	vector<int> answer(q);
	for(int i=0; i<n; i++){
        arr[i+1]=A[i];
	}
	makebucket();
	int ans=0;
	for(int i=2; i<=n; i++){
        ans+=query(1, i, arr[i]);
	}
	for(int j=0; j<X.size(); j++){
        int i=X[j]+1;
		int temp1=query(1, i, arr[i]);
		int temp2=n-i+1-query(i, n, arr[i]-1);
		ans-=temp1;
		ans-=temp2;
		update(i, V[j]);
		//print();
        temp1=query(1, i, arr[i]);
        temp2=n-i+1-query(i, n, arr[i]-1);
        ans+=temp1;
        ans+=temp2;
        answer[j]=ans;
	}
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'void print()':
bubblesort2.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<bucket[i].size(); j++)printf("%d ", bucket[i][j]);
                      ~^~~~~~~~~~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:71:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0; j<X.size(); j++){
               ~^~~~~~~~~

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