Submission #1023476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1023476		NintsiChkhaidze	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2872 ms	114472 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#define pii pair <int,int>
#define s second
#define f first
#define pb push_back
using namespace std;
 
const int N = 1e6 + 5;
int lz[4*N],AA[N],VV[N];
pii t[4*N];
map <int,int> l1;
 
void build(int h,int l,int r){
	if (l == r){
		t[h] = {0,l};
		return;
	}
	build(left);
	build(right);
	t[h] = max(t[h*2],t[h*2 + 1]);
}
 
void push(int h){
	if (lz[h]==0) return ;
	lz[h*2] += lz[h];
	lz[h*2 + 1] += lz[h];
	t[h*2].f += lz[h];
	t[h*2 + 1].f += lz[h];
	lz[h] = 0;
}
 
void upd(int h,int l,int r,int L,int R,int val){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		t[h].f += val;
		lz[h] += val;
		return;
	}
	push(h);
	upd(left,L,R,val);
	upd(right,L,R,val);
	t[h] = max(t[h*2],t[h*2 + 1]);
}
 
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	vector <pair <pii,int> > vec;
	for (int i=0;i<A.size();i++){
		vec.pb({{A[i],i},1});
	}
	for (int i=0;i<V.size();i++){
		vec.pb({{V[i],i},2});
	}
	sort(vec.begin(),vec.end());
	
	int m = vec.size();
	for (int i = 0; i < vec.size(); i++){
		int tp = vec[i].s;
		if (tp == 1) AA[vec[i].f.s] = i + 1;
		else VV[vec[i].f.s] = i + 1;
		if (!i || vec[i].f.f != vec[i - 1].f.f)
			l1[vec[i].f.f] = i + 1;
	}
	
	build(1,1,m);
	for (int i = 0; i < A.size(); i++){
		upd(1,1,m,l1[A[i]],m,-1);
		upd(1,1,m,AA[i],AA[i],i+1);
	}
	
	int Q=X.size();
	vector<int> answer(Q);
	
	for (int j = 0; j < X.size(); j++){
      
		int i = X[j];
		upd(1,1,m,l1[A[i]],m,+1);
		upd(1,1,m,AA[i],AA[i],-i-1);
		
		A[i] = V[j];
		AA[i] = VV[j];
		
		upd(1,1,m,l1[A[i]],m,-1);
		upd(1,1,m,AA[i],AA[i],i+1);
		answer[j] = t[1].f;
	}
	
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i=0;i<A.size();i++){
      |               ~^~~~~~~~~
bubblesort2.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for (int i=0;i<V.size();i++){
      |               ~^~~~~~~~~
bubblesort2.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 0; i < vec.size(); i++){
      |                  ~~^~~~~~~~~~~~
bubblesort2.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for (int i = 0; i < A.size(); i++){
      |                  ~~^~~~~~~~~~
bubblesort2.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for (int j = 0; j < X.size(); j++){
      |                  ~~^~~~~~~~~~

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