제출 #1156030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156030		Hamed_Ghaffari	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1629 ms	151856 KiB

bubblesort2

#include "bubblesort2.h"
#include<bits/stdc++.h>
using namespace std;

#define SZ(x) int(x.size())
#define lc (id<<1)
#define rc (lc|1)
#define mid ((l+r)>>1)
#define all(x) x.begin(), x.end()
#define pb push_back

const int MXN = 1e6+5;

int seg[MXN<<2], lz[MXN<<2], N;
void upd(int s, int e, int x, int l=0, int r=N, int id=1) {
	if(s<=l && r<=e) {
		seg[id] += x;
		lz[id] += x;
		return;
	}
	if(s<mid) upd(s, e, x, l, mid, lc);
	if(e>mid) upd(s, e, x, mid, r, rc);
	seg[id] = max(seg[lc], seg[rc]) + lz[id];
}

vector<int> cmp;
inline int GI(int x) { return lower_bound(all(cmp), x)-cmp.begin(); }
set<int> pos[MXN];

inline void erase(int i, int ai) {
	upd(ai, N, 1);
	if(i==(*pos[ai].rbegin()))
		upd(ai, ai+1, -i + (*prev(prev(pos[ai].end()))));
	pos[ai].erase(i);
}

inline void insert(int i, int ai) {
	upd(ai, N, -1);
	if(i>(*pos[ai].rbegin()))
		upd(ai, ai+1, -(*pos[ai].rbegin())+i);
	pos[ai].insert(i);
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int n = SZ(A), q = SZ(X);
	for(int i=0; i<n; i++) cmp.pb(A[i]);
	for(int i=0; i<q; i++) cmp.pb(V[i]);
	sort(all(cmp));
	cmp.resize(unique(all(cmp))-cmp.begin());
	N = SZ(cmp);
	for(int i=0; i<N; i++) pos[i].insert(-1);
	for(int i=0; i<n; i++) A[i] = GI(A[i]);
	for(int i=0; i<q; i++) V[i] = GI(V[i]);
	for(int i=0; i<n; i++) insert(i, A[i]);
	vector<int> ans(q);
	for(int i=0; i<q; i++) {
		erase(X[i], A[X[i]]);
		insert(X[i], A[X[i]]=V[i]);
		ans[i] = seg[1];
	}
	return ans;
}

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