Submission #730930

#	Time	Username	Problem	Language	Result	Execution time	Memory
730930		esomer	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	2899 ms	147420 KiB

bubblesort2

#include<bits/stdc++.h>
#include "bubblesort2.h"
 
using namespace std;
 
#define endl "\n"
 
typedef long long int ll;
 
const int MOD = 1e9 + 7;
 
struct segTree{
	vector<int> v;
	vector<int> upd;
	int siz;
	void init(int n){
		siz = 1;
		while(siz < n) siz *= 2;
		v.assign(2 * siz, 0);
		upd.assign(2 * siz, 0);
	}
	
	void set(int l, int r, int u, int x, int lx, int rx){
		if(lx >= l && rx <= r){
			upd[x] += u;
			v[x] += u;
			return;
		}
		if(lx >= r || rx <= l) return;
		int m = (lx + rx) / 2;
		set(l, r, u, 2 * x + 1, lx, m);
		set(l, r, u, 2 * x + 2, m, rx);
		v[x] = max(v[2 * x + 1], v[2 * x + 2]) + upd[x];
	}
	
	void set(int l, int r, int u){
		set(l, r, u, 0, 0, siz);
	}
	
	int get_ans(){
		return v[0];
	}
};
 
vector<int> countScans(vector<int> A,vector<int> V1,vector<int> V2){
	int n = (int)A.size();
	int q = (int)V1.size();
	vector<int> all(n + q);
	for(int i = 0; i < n; i++) all[i] = A[i];
	for(int i = 0; i < q; i++) all[i + n] = V2[i];
	sort(all.begin(), all.end());
	unordered_map<int, int> m;
	int curr = 0;
	for(int i = 0; i < n + q; i++){
		if(i == 0) {m[all[i]] = curr; curr++;}
		else{
			if(all[i] == all[i-1]) continue;
			m[all[i]] = curr;
			curr++;
		}
	}
	segTree st; st.init(curr);
	vector<set<int>> pos(curr);
	for(int i = 0; i < n; i++){
		pos[m[A[i]]].insert(i);
		st.set(m[A[i]], curr, -1);
	}
	for(int i = 0; i < curr; i++){
		if((int)pos[i].size() > 0){
			st.set(i, i + 1, *pos[i].rbegin()+1);
		}
	}
	vector<int> ans(q);
	for(int qq = 0; qq < q; qq++){
		int i = V1[qq];
		int lst = A[i];
		int nw = V2[qq];
		A[i] = nw;
		lst = m[lst];
		nw = m[nw];
		int lst_pos = *pos[lst].rbegin();
		pos[lst].erase(i);
		if((int)pos[lst].size() > 0) st.set(lst, lst + 1, (*pos[lst].rbegin() - lst_pos));
		else st.set(lst, lst + 1, -lst_pos - 1);
		st.set(lst, curr, 1);
		if((int)pos[nw].size() == 0){
			pos[nw].insert(i);
			st.set(nw, nw + 1, i+1);
		}else{
			lst_pos = *pos[nw].rbegin();
			pos[nw].insert(i);
			st.set(nw, nw + 1, (*pos[nw].rbegin() - lst_pos));
		}
		st.set(nw, curr, -1);
		ans[qq] = st.get_ans();
	}
	return ans;
}

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