제출 #102674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
102674		tincamatei	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2613 ms	130032 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

const int MAX_N = 500000;
const int MAX_Q = 500000;
const int MAX_VALS = MAX_N + MAX_Q;
const int INF = 1000000000;

struct Aint {
	int aint[1+4*MAX_VALS];
	int lazy[1+4*MAX_VALS];
	set<int> poz[MAX_VALS];
	int maxr;
	int higher;

	int getbest(int val) {
		if(poz[val].empty())
			return -INF;
		else
			return *(poz[val].rbegin());
	}

	void build(int nod, int l, int r) {
		int mid = (l + r) / 2;
		lazy[nod] = 0;

		if(l == r) {
			higher -= poz[l].size();
			aint[nod] = getbest(l) + higher;
		} else if(l < r) {
			build(2 * nod, l, mid);
			build(2 * nod + 1, mid + 1, r);
			aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
		}
	}

	void propagate(int nod, int l, int r) {
		aint[nod] += lazy[nod];
		if(l < r) {
			lazy[2 * nod] += lazy[nod];
			lazy[2 * nod + 1] += lazy[nod];
		}
		lazy[nod] = 0;
	}
	
	void addRange(int i, int j, int val, int l, int r, int nod) {
		propagate(nod, l, r);
		if(j < l || r < i || j < i) return ;

		if(i <= l && r <= j) {
			lazy[nod] += val;
			propagate(nod, l, r);
		} else {
			int mid = (l + r) / 2;
			addRange(i, j, val, l, mid, 2 * nod);
			addRange(i, j, val, mid + 1, r, 2 * nod + 1);

			aint[nod] = max(aint[2 * nod], aint[2 * nod + 1]);
		}
	}

	void erasePoz(int i, int val) {
		int oldpoz, newpoz;
		
		oldpoz = getbest(val);
		poz[val].erase(i);
		newpoz = getbest(val);

		addRange(val, val, -oldpoz + newpoz, 0, maxr, 1);
		addRange(0, val - 1, -1, 0, maxr, 1);
	}

	void insertPoz(int i, int val) {
		int oldpoz, newpoz;
		
		oldpoz = getbest(val);
		poz[val].insert(i);
		newpoz = getbest(val);

		addRange(val, val, -oldpoz + newpoz, 0, maxr, 1);
		addRange(0, val - 1, 1, 0, maxr, 1);
	}
	
	int query() {
		propagate(1, 0, maxr);
		return aint[1];
	}
};

struct Solver {
	int N, Q;
	int v[MAX_N], poz[MAX_Q], val[MAX_Q];
	int *p[MAX_N+MAX_Q];
	Aint *aint;

	Solver(const vector<int> &A, const vector<int> &X, const vector<int> &V) {
		N = A.size();
		Q = X.size();

		for(int i = 0; i < N; ++i)
			v[i] = A[i];
		for(int i = 0; i < Q; ++i) {
			poz[i] = X[i];
			val[i] = V[i];
		}
	}
	
	static bool cmp(int *a, int *b) {
		return *a < *b;
	}

	int normalize() {
		int top = 0;

		for(int i = 0; i < N; ++i)
			p[top++] = &v[i];
		for(int i = 0; i < Q; ++i)
			p[top++] = &val[i];

		sort(p, p + top, cmp);

		int last = *p[0], j = 0;
		for(int i = 0; i < top; ++i)
			if(*p[i] == last)
				*p[i] = j;
			else {
				last = *p[i];
				*p[i] = ++j;
			}

		return j;
	}

	vector<int> getans() {
		vector<int> ans;

		aint = new Aint();
		aint->maxr = normalize();
		aint->higher = N;

		for(int i = 0; i < N; ++i)
			aint->poz[v[i]].insert(i);
		
		aint->build(1, 0, aint->maxr);

		for(int i = 0; i < Q; ++i) {
			aint->erasePoz(poz[i], v[poz[i]]);
			aint->insertPoz(poz[i], val[i]);
			
			v[poz[i]] = val[i];

			ans.push_back(aint->query() - N + 1);
		}

		return ans;
	}
};

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
	Solver *solver = new Solver(A, X, V);

	return solver->getans();
}

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