Submission #160482

#	Time	Username	Problem	Language	Result	Execution time	Memory
160482		iefnah06	Bubble Sort 2 (JOI18_bubblesort2)	C++11	100 / 100	3129 ms	99064 KiB

bubblesort2

#include "bubblesort2.h"

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

using ll = long long;

const int INF = 1e9;

const int MAXN = 5.1e5;
const int MAXQ = 5.1e5;
const int MAXS = MAXN + MAXQ;
int N, Q;

struct seg {
	seg* ch[2];
	ll maxval;
	ll lazyval;

	seg() {
		maxval = lazyval = 0;
	}

	void increment(ll a) {
		maxval += a;
		lazyval += a;
	}

	void update() {
		assert(ch[0] && ch[1]);
		maxval = lazyval + max(ch[0]->maxval, ch[1]->maxval);
	}
};
seg nodes[MAXS*2];
int NODE = 0;
seg* ROOT;

pair<int, int> pairs[MAXS];
int S;

seg* build(int x = 0, int y = S) {
	seg* n = &nodes[NODE++];
	if (y - x > 1) {
		int z = (x + y) / 2;
		n->ch[0] = build(x, z);
		n->ch[1] = build(z, y);
		n->update();
	}
	return n;
}

void update(int l, int r, int v, int x, int y, seg* n) {
	if (l <= x && y <= r) {
		n->increment(v);
	} else {
		int z = (x + y) / 2;
		if (l < z) {
			update(l, r, v, x, z, n->ch[0]);
		}
		if (z < r) {
			update(l, r, v, z, y, n->ch[1]);
		}
		n->update();
	}
}

ll slow[MAXN];

void update(int l, int r, int v) {
	if (l < r) {
		update(l, r, v, 0, S, ROOT);
	}
}

ll query() {
	return ROOT->maxval;
}

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	N = int(A.size());
	Q = int(X.size());

	S = 0;
	for (int i = 0; i < N; i++) {
		pairs[S++] = {A[i], i};
	}
	for (int i = 0; i < Q; i++) {
		pairs[S++] = {V[i], X[i]};
	}
	sort(pairs, pairs + S);
	S = int(unique(pairs, pairs + S) - pairs);

	auto modify = [&](int v, int i, int k) -> void {
		int j = int(lower_bound(pairs, pairs + S, pair<int, int>(v, i)) - pairs);
		assert(make_pair(v, i) == pairs[j]);
		update(j, j+1, k * (INF + i));
		update(j+1, S, k * -1);
	};

	ROOT = build();
	update(0, S, -INF);
	for (int i = 0; i < N; i++) {
		modify(A[i], i, 1);
	}
	
	vector<int> answer(Q);
	for (int q = 0; q < Q; q++) {
		modify(A[X[q]], X[q], -1);
		modify(V[q], X[q], 1);
		A[X[q]] = V[q];
		answer[q] = query();
	}
	return answer;
}

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