Submission #673471

#	Time	Username	Problem	Language	Result	Execution time	Memory
673471		406	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	25 ms	25524 KiB

bubblesort2

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

const int N = 5e5 + 50;
const int INF = 1 << 25;
int mx[4 * N], mn[4 * N], sz[4 * N], ans[4 * N];
vector<int> cpX;
set<int> S[N];

void add(int v, int l, int r, int ind, int x, bool st) {
	if (r - l == 1) {
		if (st == 0) // remove
			S[l].erase(x);
		else
			S[l].insert(x);
		sz[v] = S[l].size();

		if (S[l].empty()) {
			mn[v] = INF;
			mx[v] = -INF;
		} else {
			mn[v] = *S[l].begin();
			mx[v] = *(--S[l].end());
		}
		ans[v] = 0;
		return;
	}
	int m = l + r >> 1;
	if (ind < m) add(v<<1, l, m, ind, x, st);
	else add(v<<1|1, m, r, ind, x, st);
	mx[v] = max(mx[v<<1], mx[v<<1|1]);
	mn[v] = min(mn[v<<1], mn[v<<1|1]);

	ans[v] = max({ans[v<<1], ans[v<<1|1], mx[v<<1] - mn[v<<1|1], 0});
}

int loc(int x) {
	return lower_bound(cpX.begin(), cpX.end(), x) - cpX.begin();
}

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

	cpX = X;
	cpX.insert(cpX.end(), A.begin(), A.end());
	sort(cpX.begin(), cpX.end());
	cpX.resize(unique(cpX.begin(), cpX.end()) - cpX.begin());

	for (int i = 0; i < A.size(); i++)
		add(1, 0, cpX.size(), loc(A[i]), i, 1);

	std::vector<int> answer(Q);

	for (int i = 0; i < Q; i++) {
		add(1, 0, cpX.size(), loc(A[X[i]]), X[i], 0);
		add(1, 0, cpX.size(), loc(V[i]), X[i], 1);
		A[X[i]] = V[i];
		answer[i] = ans[1];
	}
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'void add(int, int, int, int, int, bool)':
bubblesort2.cpp:29:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |  int m = l + r >> 1;
      |          ~~^~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:50:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = 0; i < A.size(); i++)
      |                  ~~^~~~~~~~~~

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