Submission #1113913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113913		Paz15	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3021 ms	224240 KiB

bubblesort2

//fast
#include<bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
typedef long long ll;
typedef long double ld;

#define all(x) x.begin(),x.end()
#define rep(n) for (int i = 0 ; i<n ; i++)
#define pb push_back

const int base = (1<<20);
int maks[base*2];
int sum[base*2];
set<int> pos[base];
int stala[base];

void printout(){
	cout << "   " << maks[1] << '\n';
	cout << " " << maks[2] << "  " << maks[3] << '\n';
	cout << maks[4] << ' ' << maks[5] << ' ' << maks[6] << ' ' << maks[7] << '\n';
	cout << "   " << sum[1] << '\n';
	cout << " " << sum[2] << "  " << sum[3] << '\n';
	cout << sum[4] << ' ' << sum[5] << ' ' << sum[6] << ' ' << sum[7] << '\n';
	cout << stala[0] << ' ' << stala[1] << ' ' << stala[2] << ' ' << stala[3] << '\n';
}

void dodaj(int l, int r, int p, int k, int w, int c){
	if (k<l || r<p) return;
	if (p<=l && r<=k){
		sum[w]+=c;
		maks[w]+=c;
		return;
	}
	dodaj(l,(l+r)/2,p,k,w*2,c);
	dodaj((l+r)/2+1,r,p,k,w*2+1,c);
	maks[w] = max(maks[w*2],maks[w*2+1])+sum[w];
}

void ustaw(int a, int b){
	sum[a+base]-=stala[a];
	stala[a] = b;
	sum[a+base]+=stala[a];
	a+=base;
	maks[a] = sum[a];
	a/=2;
	while (a>=1){
		maks[a] = max(maks[a*2],maks[a*2+1])+sum[a];
		a/=2;
	}
}

map<int,int> tosmall;
int tobig[base];

vector<int> countScans(vector<int> a, vector<int> x, vector<int> v){
	int n = a.size(), q = x.size();
	vector<int> odp(q);
	vector<int> move;
	rep(n){
		move.pb(a[i]);
	}
	rep(q){
		move.pb(v[i]);
	}
	int c = -1;
	int last = -2137;
	sort(all(move));
	for (int i : move){
		if (i!=last){
			last = i;
			c++;
			tobig[c] = i;
			tosmall[i] = c;
		}
	}
	rep(base){
		pos[i].insert(-1e8);
	}
	rep(n){
		a[i] = tosmall[a[i]];
		pos[a[i]].insert(i);
		dodaj(0,base-1,a[i],base-1,1,-1);
	}
	rep(base){
		auto it = pos[i].end();
		it--;
		ustaw(i,*it);
	}
	rep(q){
		int old = a[x[i]];
		int nowy = tosmall[v[i]];
		a[x[i]] = nowy;
		pos[old].erase(x[i]);
		pos[nowy].insert(x[i]);
		dodaj(0,base-1,old,base-1,1,1);
		dodaj(0,base-1,nowy,base-1,1,-1);
		auto it = pos[old].end();
		it--;
		ustaw(old,*it);
		auto it1 = pos[nowy].end();
		it1--;
		ustaw(nowy,*it1);
		odp[i] = maks[1]+1;
		//printout();
	}
	return odp;
}

/*int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	int n,q;
	cin >> n >> q;
	vector<int> a(n);
	vector<int> x(q);
	vector<int> v(q);
	rep(n) cin >> a[i];
	rep(q) cin >> x[i] >> v[i];
	vector<int> odp = countScans(a,x,v);
	for (int i : odp) cout << i << '\n';
}*/

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