oj.uz

Submission #673471

# Submission time Handle Problem Language Result Execution time Memory
673471 2022-12-20T16:35:36 Z 406 Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 25 ms 25524 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 25524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23892 KB Output isn't correct
2 Halted 0 ms 0 KB -