Submission #1055090

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055090		aymanrs	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	833 ms	65680 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
const int N = 1e6;
int ind[N];
int st[4*N+10], lz[4*N+10] = {0};
int cons(int i, int l, int r){
	if(l==r) return st[i] = ind[l];
	int m = l+r>>1;
	return st[i] = max(cons(i<<1, l, m),cons(i<<1|1, m+1, r));
}
void upd(int i, int l, int r, int a, int v){
	if(lz[i]){
		st[i]+=lz[i];
		if(l!=r){
			lz[i<<1]+=lz[i];
			lz[i<<1|1] += lz[i];
		}
		lz[i]=0;
	}
	if(r<a)return;
	if(a<=l){
		st[i]+=v;
		if(l!=r){
			lz[i<<1]+=v;
			lz[i<<1|1]+=v;
		}
		return;
	}
	int m = l+r>>1;
	upd(i<<1, l, m, a, v);
	upd(i<<1|1, m+1, r, a, v);
	st[i]=max(st[i<<1],st[i<<1|1]);
}
void updind(int i, int l, int r, int iind, int newind){
	if(lz[i]){
		st[i]+=lz[i];
		if(l!=r){
			lz[i<<1]+=lz[i];
			lz[i<<1|1] += lz[i];
		}
		lz[i]=0;
	}
	if(l==r){
		st[i] += newind-ind[l];
		ind[l] = newind;
		return;
	}
	int m = l+r>>1;
	if(iind <= m) updind(i<<1, l, m, iind, newind);
	else updind(i<<1|1, m+1, r, iind, newind);
	st[i] = max(st[i<<1]+lz[i<<1], st[i<<1|1]+lz[i<<1|1]);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int n=A.size(), q = X.size();
	long long a[n], v[q], tot[n+q];for(int i = 0;i < n;i++) tot[i] = a[i] = (long long)A[i]*n+i;
	for(int i = 0;i < q;i++) tot[i+n] = v[i] = (long long)V[i]*n+X[i];
	sort(tot, tot+n+q);
	fill(ind,ind+N,-1);
	for(int i = 0;i < n;i++) {
		a[i] = lower_bound(tot, tot+n+q, a[i])-tot;
		ind[a[i]]=i;
	}
	for(int i = 0;i < q;i++) v[i] = lower_bound(tot, tot+n+q, v[i])-tot;
	cons(1, 0, N-1);
	for(int i = 0;i < n;i++){
		upd(1, 0, N-1, a[i]+1, -1);
	}
	vector<int> ans(q);
	for(int _ = 0;_ < q;_++){
		int i = X[_];
		updind(1, 0, N-1, a[i], -1);
		updind(1, 0, N-1, v[_], i);
		upd(1, 0, N-1, a[i]+1, 1);
		upd(1, 0, N-1, v[_]+1, -1);
		a[i]=v[_];
		ans[_]=st[1];
	}
	return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'int cons(int, int, int)':
bubblesort2.cpp:11:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   11 |  int m = l+r>>1;
      |          ~^~
bubblesort2.cpp: In function 'void upd(int, int, int, int, int)':
bubblesort2.cpp:32:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |  int m = l+r>>1;
      |          ~^~
bubblesort2.cpp: In function 'void updind(int, int, int, int, int)':
bubblesort2.cpp:51:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |  int m = l+r>>1;
      |          ~^~

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