Submission #412406

#	Time	Username	Problem	Language	Result	Execution time	Memory
412406		nichke	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	97 ms	98936 KiB

bubblesort2

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

const int mxn = 1e6 + 100;
vector<int> a, pos, val, ans;

int timer;
map<int, int> mp;
set<int> ind[mxn];
int tree[4 * mxn], lazy[4 * mxn], lz[4 * mxn];

void push(int v, int l, int r) {
	if (r < l) return;
	if (lz[v] != 0) {
		tree[v] += lazy[v];
		if (l != r) {
			lz[2 * v + 1] = 1;
			lz[2 * v + 2] = 1;
			tree[2 * v + 1] += lazy[v];
			tree[2 * v + 2] += lazy[v];
		}
		lazy[v] = 0;
		lz[v] = 0;
	}
}

void update(int v, int tl, int tr, int ql, int qr, int val) {
	push(v, tl, tr);
	if (tl > tr || tl > qr || tr < ql) return;
	if (tl >= ql && tr <= qr) {
		lz[v] = 1;
		lazy[v] += val;
		push(v, tl, tr);
		return;
	}
	int tm = (tl + tr) / 2;
	update(2 * v + 1, tl, tm, ql, qr, val);
	update(2 * v + 2, tm + 1, tr, ql, qr, val);
	tree[v] = max(tree[2 * v + 1], tree[2 * v + 2]);
}

void rem(int v, int x) {
	update(0, 0, timer - 1, x, timer - 1, 1);
	if (v == *ind[v].rbegin()) {
		auto it = ind[v].rbegin();
		int val = -*it;
		it--;
		val += *it;
		update(0, 0, timer - 1, x, x, val);
	}
	ind[x].erase(v);
}

void add(int v, int x) {
	update(0, 0, timer - 1, x, timer - 1, -1);
	if (v > *ind[x].rbegin()) {
		update(0, 0, timer - 1, x, x, v - *ind[x].rbegin());
	}
	ind[x].insert(v);
	a[v] = x;
}

void solve() {
	for (auto it : a) mp[it] = 1;
	for (auto it : val) mp[it] = 1;
	for (auto &it : mp) {
		it.second = timer++;
	}
	for (int i = 0; i < timer; i++) {
		ind[i].insert(-mxn);
	}
	for (int i = 0; i < a.size(); i++) {
		a[i] = mp[a[i]];
		ind[a[i]].insert(i);
		update(0, 0, timer - 1, a[i], timer - 1, -1);
	}
	for (int i = 0; i < timer; i++) {
		update(0, 0, timer - 1, i, i, *ind[i].rbegin());
	}
	for (int q = 0; q < pos.size(); q++) {
		rem(pos[q], a[pos[q]]);
		add(pos[q], mp[val[q]]);
		ans.push_back(tree[0] + 1);
	}
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
	a = A;
	pos = X;
	val = V;
	solve();
	return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'void solve()':
bubblesort2.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
bubblesort2.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int q = 0; q < pos.size(); q++) {
      |                  ~~^~~~~~~~~~~~

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