Submission #69331

#	Time	Username	Problem	Language	Result	Execution time	Memory
69331		ekrem	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	8940 ms	395664 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
#define orta ((bas + son)/2)
#define sol (k+k)
#define sag (k+k+1)
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define N 1000005
using namespace std;

typedef vector < int > vi;
int n, m, q, yer[4*N], yerl[4*N], cvp[4*N], cvpl[4*N];
set < int > s[N];
map < int , int > ek;
unordered_map < int , int > ne;
map < int , int > :: iterator it;

void yerput(int k, int bas, int son, int l);

void yerpush(int k, int bas, int son);

void yerset(int k, int bas, int son, int x, int y);

void yerup(int k, int bas, int son, int x, int y, int z);

int yerqu(int k, int bas, int son, int x);

int yersor(int k, int bas, int son, int x, int y);

void cvpput(int k, int bas, int son, int l);

void cvppush(int k, int bas, int son);

void cvpset(int k, int bas, int son, int x, int y);

void cvpup(int k, int bas, int son, int x, int y, int z);

int cvpqu(int k, int bas, int son, int x);


vi countScans(vi a, vi b, vi c){
	vi ans;
	n = a.size();
	q = b.size();
	for(int i = 0; i < n; i++)
		ek[a[i]] = 1;
	for(int i = 0; i < q; i++)
		ek[c[i]] = 1;
	for(it = ek.begin(); it != ek.end(); it++)
		ne[it->st] = ++m;
	for(int i = 0; i < n; i++)
		s[ne[a[i]]].insert(i);
	vi d = a;
	sort(d.begin(), d.end());
	for(int i = 0; i < n; i++){
		if(i + 1 != n and d[i + 1] == d[i])
			continue;
		yerset(1, 1, m, ne[d[i]], i);
	}
	for(int i = 0; i < n; i++){
		int son = *s[ne[a[i]]].rbegin();
		int yr = yerqu(1, 1, m, ne[a[i]]);
		cvpset(1, 1, m, ne[a[i]], son - yr);
	}
	for(int i = 0; i < q; i++){
		int yr = b[i];
		int yeni = ne[c[i]];
		int eski = ne[a[b[i]]];
		a[yr] = c[i];
		if(yeni == eski){
			ans.pb(cvp[1]);
			continue;
		}
		s[eski].erase(yr);
		s[yeni].insert(yr);
		if(eski < yeni){
			yerup(1, 1, m, eski, yeni - 1, -1);
			cvpup(1, 1, m, eski + 1, yeni - 1, 1);
			if(!s[eski].empty())
				cvpset(1, 1, m, eski, *s[eski].rbegin() - yerqu(1, 1, m, eski) );
			else{
				// yerset(1, 1, m, eski, -1);
				cvpset(1, 1, m, eski, 0);
			}
			if(s[yeni].size() == 1)
				yerset(1, 1, m, yeni, yersor(1, 1, m, 1, yeni - 1) + 1);
			cvpset(1, 1, m, yeni, *s[yeni].rbegin() - yerqu(1, 1, m, yeni) );
		}
		if(eski > yeni){
			yerup(1, 1, m, yeni, eski - 1, 1);
			cvpup(1, 1, m, yeni + 1, eski - 1, -1);
			if(!s[eski].empty())
				cvpset(1, 1, m, eski, *s[eski].rbegin() - yerqu(1, 1, m, eski) );
			else{
				// yerset(1, 1, m, eski, -1);
				cvpset(1, 1, m, eski, 0);
			}
			if(s[yeni].size() == 1)
				yerset(1, 1, m, yeni, yersor(1, 1, m, 1, yeni - 1) + 1);
			cvpset(1, 1, m, yeni, *s[yeni].rbegin() - yerqu(1, 1, m, yeni) );
		}
		ans.pb(cvp[1]);
	}
	return ans;
}

// int main(){
// 	freopen("in.txt", "r", stdin);
// 	freopen("out.txt", "w", stdout);
// 	int n,q;
// 	scanf("%d %d",&n ,&q);	
// 	vi a(n);
// 	for(int i=0;i<n;i++)
// 		scanf("%d",&a[i]);
// 	vi b(q), c(q);
// 	for(int j=0;j<q;j++){
// 		scanf("%d %d",&b[j], &c[j]);
// 	}
// 	vi cvp = countScans(a, b, c);
// 	for(int j=0;j<int(cvp.size());j++)
// 		printf("%d\n",cvp[j]);
// }

void yerput(int k, int l){
	yer[k] += l;
	yerl[k] += l;
}

void yerpush(int k){
	yerput(sol, yerl[k]);
	yerput(sag, yerl[k]);
	yerl[k] = 0;
}

void yerset(int k, int bas, int son, int x, int y){
	if(bas == son){
		yer[k] = y;
		return;
	}
	yerpush(k);
	if(x <= orta)
		yerset(sol, bas, orta, x, y);
	else
		yerset(sag, orta + 1, son, x, y);
	yer[k] = max(yer[sol] , yer[sag]);
}

void yerup(int k, int bas, int son, int x, int y, int z){
	if(bas > y or son < x)
		return;
	if(bas >= x and son <= y){
		yerput(k, z);
		return;
	}
	yerpush(k);
	yerup(sol, bas, orta, x, y, z);
	yerup(sag, orta + 1, son, x, y, z);
	yer[k] = max(yer[sol] , yer[sag]);
}

int yerqu(int k, int bas, int son, int x){
	if(bas == son)
		return yer[k];
	yerpush(k);
	if(x <= orta)
		return yerqu(sol, bas, orta, x);
	return yerqu(sag, orta + 1, son, x);
}

int yersor(int k, int bas, int son, int x, int y){
	if(bas > y or son < x)
		return -1;
	if(bas >= x and son <= y)
		return yer[k];
	return max(yersor(sol, bas, orta , x, y), yersor(sag, orta + 1, son, x, y));
}

void cvpput(int k, int l){
	cvp[k] += l;
	cvpl[k] += l;
}

void cvppush(int k){
	cvpput(sol, cvpl[k]);
	cvpput(sag, cvpl[k]);
	cvpl[k] = 0;
}

void cvpset(int k, int bas, int son, int x, int y){
	if(bas == son){
		cvp[k] = y;
		return;
	}
	cvppush(k);
	if(x <= orta)
		cvpset(sol, bas, orta, x, y);
	else
		cvpset(sag, orta + 1, son, x, y);
	cvp[k] = max(cvp[sol] , cvp[sag]);
}

void cvpup(int k, int bas, int son, int x, int y, int z){
	if(bas > y or son < x)
		return;
	if(bas >= x and son <= y){
		cvpput(k, z);
		return;
	}
	cvppush(k);
	cvpup(sol, bas, orta, x, y, z);
	cvpup(sag, orta + 1, son, x, y, z);
	cvp[k] = max(cvp[sol] , cvp[sag]);
}

int cvpqu(int k, int bas, int son, int x){
	if(bas == son)
		return cvp[k];
	cvppush(k);
	if(x <= orta)
		return cvpqu(sol, bas, orta, x);
	return cvpqu(sag, orta + 1, son, x);
}

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