oj.uz

Submission #99760

# Submission time Handle Problem Language Result Execution time Memory
99760 2019-03-06T22:51:01 Z luciocf Bubble Sort 2 (JOI18_bubblesort2) C++14
38 / 100
 81 ms 50060 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

const int maxn = 1e6+10;

int n;

int num[maxn], qtd[maxn], soma[maxn];

int tree[4*maxn], lazy[4*maxn];

set<int> Pos[maxn];

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node] = -soma[l-1]-(*Pos[l].begin());
		return;
	}

	int mid = (l+r)>>1;

	build(2*node, l, mid); build(2*node+1, mid+1, r);

	tree[node] = max(tree[2*node], tree[2*node+1]);
}

void flush(int node, int l, int r)
{
	if (!lazy[node]) return;

	if (l != r)
	{
		lazy[2*node] += lazy[node];
		lazy[2*node+1] += lazy[node];
	}

	tree[node] += lazy[node];

	lazy[node] = 0;
}

void upd(int node, int l, int r, int a, int b, int v)
{
	if (l > r) return;

	flush(node, l, r);
	if (l > b || r < a) return;

	if (l >= a && r <= b)
	{
		lazy[node] += v;
		flush(node, l, r);
		return;
	}

	int mid = (l+r)>>1;

	upd(2*node, l, mid, a, b, v); upd(2*node+1, mid+1, r, a, b, v);

	tree[node] = max(tree[2*node], tree[2*node+1]);
}

int query(int node, int l, int r, int a, int b)
{
	flush(node, l, r);
	if (l > b || r < a) return -4*maxn;
	if (l >= a && r <= b) return tree[node];

	int mid = (l+r)>>1;

	return max(query(2*node, l, mid, a, b), query(2*node+1, mid+1, r, a, b));
}

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

	vector<int> C;
	map<int, int> Mp;

	for (int i = 0; i < n; i++) C.push_back(A[i]);
	for (int i = 0; i < V.size(); i++) C.push_back(V[i]);

	sort(C.begin(), C.end());

	int ind = 0;
	for (auto x: C)
		if (Mp.find(x) == Mp.end())
			Mp[x] = ++ind, Pos[ind].insert(4*maxn);

	for (int i = 0; i < n; i++)
	{
		num[i] = Mp[A[i]];

		qtd[num[i]]++;
		Pos[num[i]].insert(-i);
	}

	for (int i = 1; i <= ind; i++)
		soma[i] = soma[i-1] + qtd[i];

	build(1, 1, ind);

	vector<int> ans;

	for (int i = 0; i < V.size(); i++)
	{
		int pos = X[i], v = Mp[V[i]];

		upd(1, 1, ind, num[pos]+1, ind, 1);

		bool last = 0;

		if (pos == -(*Pos[num[pos]].begin())) last = 1;

		Pos[num[pos]].erase(-pos);

		if (last) upd(1, 1, ind, num[pos], num[pos], -(*Pos[num[pos]].begin())-pos);

		num[pos] = v;

		upd(1, 1, ind, v, v, *Pos[v].begin());

		Pos[v].insert(-pos);

		upd(1, 1, ind, v+1, ind, -1);
		upd(1, 1, ind, v, v, -(*Pos[v].begin()));

		ans.push_back(query(1, 1, ind, 1, ind));
	}

	return ans;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++) C.push_back(V[i]);
                  ~~^~~~~~~~~~
bubblesort2.cpp:110:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < V.size(); i++)
                  ~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47480 KB Output is correct
2 Correct 50 ms 47608 KB Output is correct
3 Correct 51 ms 47992 KB Output is correct
4 Correct 54 ms 47992 KB Output is correct
5 Correct 48 ms 48000 KB Output is correct
6 Correct 59 ms 47992 KB Output is correct
7 Correct 49 ms 47992 KB Output is correct
8 Correct 47 ms 48000 KB Output is correct
9 Correct 48 ms 48120 KB Output is correct
10 Correct 47 ms 47864 KB Output is correct
11 Correct 50 ms 47928 KB Output is correct
12 Correct 47 ms 47992 KB Output is correct
13 Correct 51 ms 48000 KB Output is correct
14 Correct 48 ms 47960 KB Output is correct
15 Correct 47 ms 47864 KB Output is correct
16 Correct 59 ms 47868 KB Output is correct
17 Correct 50 ms 47864 KB Output is correct
18 Correct 51 ms 48000 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47480 KB Output is correct
2 Correct 50 ms 47608 KB Output is correct
3 Correct 51 ms 47992 KB Output is correct
4 Correct 54 ms 47992 KB Output is correct
5 Correct 48 ms 48000 KB Output is correct
6 Correct 59 ms 47992 KB Output is correct
7 Correct 49 ms 47992 KB Output is correct
8 Correct 47 ms 48000 KB Output is correct
9 Correct 48 ms 48120 KB Output is correct
10 Correct 47 ms 47864 KB Output is correct
11 Correct 50 ms 47928 KB Output is correct
12 Correct 47 ms 47992 KB Output is correct
13 Correct 51 ms 48000 KB Output is correct
14 Correct 48 ms 47960 KB Output is correct
15 Correct 47 ms 47864 KB Output is correct
16 Correct 59 ms 47868 KB Output is correct
17 Correct 50 ms 47864 KB Output is correct
18 Correct 51 ms 48000 KB Output is correct
19 Correct 71 ms 49716 KB Output is correct
20 Correct 76 ms 49924 KB Output is correct
21 Correct 72 ms 50040 KB Output is correct
22 Correct 79 ms 50060 KB Output is correct
23 Correct 68 ms 49716 KB Output is correct
24 Correct 73 ms 49784 KB Output is correct
25 Correct 81 ms 49628 KB Output is correct
26 Correct 72 ms 49656 KB Output is correct
27 Correct 68 ms 49528 KB Output is correct
28 Correct 70 ms 49528 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 47480 KB Output is correct
2 Correct 50 ms 47608 KB Output is correct
3 Correct 51 ms 47992 KB Output is correct
4 Correct 54 ms 47992 KB Output is correct
5 Correct 48 ms 48000 KB Output is correct
6 Correct 59 ms 47992 KB Output is correct
7 Correct 49 ms 47992 KB Output is correct
8 Correct 47 ms 48000 KB Output is correct
9 Correct 48 ms 48120 KB Output is correct
10 Correct 47 ms 47864 KB Output is correct
11 Correct 50 ms 47928 KB Output is correct
12 Correct 47 ms 47992 KB Output is correct
13 Correct 51 ms 48000 KB Output is correct
14 Correct 48 ms 47960 KB Output is correct
15 Correct 47 ms 47864 KB Output is correct
16 Correct 59 ms 47868 KB Output is correct
17 Correct 50 ms 47864 KB Output is correct
18 Correct 51 ms 48000 KB Output is correct
19 Correct 71 ms 49716 KB Output is correct
20 Correct 76 ms 49924 KB Output is correct
21 Correct 72 ms 50040 KB Output is correct
22 Correct 79 ms 50060 KB Output is correct
23 Correct 68 ms 49716 KB Output is correct
24 Correct 73 ms 49784 KB Output is correct
25 Correct 81 ms 49628 KB Output is correct
26 Correct 72 ms 49656 KB Output is correct
27 Correct 68 ms 49528 KB Output is correct
28 Correct 70 ms 49528 KB Output is correct
29 Incorrect 59 ms 49272 KB Output isn't correct
30 Halted 0 ms 0 KB -