Submission #445000

#	Time	Username	Problem	Language	Result	Execution time	Memory
445000		Petremol	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	6755 ms	12156 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define inf (int)(1e17+1)
#define mod (int)(1e9+7)
#define N (int)(5e5+5)
#define fi first
#define se second
#define endl "\n"
#define eps (double)(1e-9)
#define sa cout<<"sa"<<endl
using namespace std;

struct segtree{
	int n;
	vector <vector<int>> seg;

	segtree(int n) : n(n), seg(4*n){};

	void update(int x,int a,int j,int l,int r){
		if(l==r) {seg[j].clear();seg[j].push_back(x);return;}
		int m=(l+r)>>1;
		if(a<=m) update(x,a,2*j,l,m);
		else update(x,a,2*j+1,m+1,r);
		seg[j].clear();
		int cura=0,curb=0;
		while((cura!=seg[2*j].size())&&(curb!=seg[2*j+1].size())){
			if(seg[2*j][cura]<seg[2*j+1][curb])
				seg[j].push_back(seg[2*j][cura++]);
			else seg[j].push_back(seg[2*j+1][curb++]);
		}
		while(cura!=seg[2*j].size()) seg[j].push_back(seg[2*j][cura++]);
		while(curb!=seg[2*j+1].size()) seg[j].push_back(seg[2*j+1][curb++]);	
	}

	int query(int x,int a,int b,int j,int l,int r){
		if(a>r||b<l) return 0;

		if(a<=l&&r<=b) return lower_bound(all(seg[j]),x)-seg[j].begin();

		int m=(l+r)>>1;
		
		return query(x,a,b,2*j,l,m)+query(x,a,b,2*j+1,m+1,r);
	}

	int query(int x,int l,int r) {return query(x,l,r,1,0,n-1);}

	void update(int x,int i) {update(x,i,1,0,n-1);}
};

vector<int> countScans(vector<int> a,vector<int> x,vector<int> v){
	int n=a.size();
	int q=x.size();
	vector<int> ans(q);
	segtree seg1(n),seg2(n);
	int cur=0;
	for(int i=0;i<n;i++) {
		seg1.update(a[i],i);
		seg2.update(-a[i],i);
	}
	for(int i=0;i<n;i++) cur+=seg1.query(a[i],i,n-1);
	for(int i=0;i<q;i++){
		int id=x[i];
		cur-=seg1.query(a[id],id,n-1)+seg2.query(-a[id],0,id);
		seg1.update(v[i],id);
		seg2.update(-v[i],id);
		cur+=seg1.query(a[id],id,n-1)+seg2.query(-a[id],0,id);
		ans[i]=cur;
	}

	return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In member function 'void segtree::update(int, int, int, int, int)':
bubblesort2.cpp:27:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   while((cura!=seg[2*j].size())&&(curb!=seg[2*j+1].size())){
      |          ~~~~^~~~~~~~~~~~~~~~~
bubblesort2.cpp:27:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   while((cura!=seg[2*j].size())&&(curb!=seg[2*j+1].size())){
      |                                   ~~~~^~~~~~~~~~~~~~~~~~~
bubblesort2.cpp:32:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   while(cura!=seg[2*j].size()) seg[j].push_back(seg[2*j][cura++]);
      |         ~~~~^~~~~~~~~~~~~~~~~
bubblesort2.cpp:33:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   while(curb!=seg[2*j+1].size()) seg[j].push_back(seg[2*j+1][curb++]);
      |         ~~~~^~~~~~~~~~~~~~~~~~~

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