답안 #99759 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99759	2019-03-06T22:35:59 Z	luciocf	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	84 ms	50184 KB

bubblesort2

#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)
	{
		if (!Pos[l].empty()) tree[node] = -soma[l-1]-(*Pos[l].begin());
		else tree[node] = -3*maxn;
		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 -2*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(3*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:87: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:111: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

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	47480 KB	Output is correct
2	Correct	47 ms	47616 KB	Output is correct
3	Correct	51 ms	47992 KB	Output is correct
4	Correct	53 ms	47992 KB	Output is correct
5	Correct	59 ms	47992 KB	Output is correct
6	Correct	55 ms	48060 KB	Output is correct
7	Correct	49 ms	47992 KB	Output is correct
8	Correct	51 ms	47992 KB	Output is correct
9	Correct	54 ms	48120 KB	Output is correct
10	Correct	50 ms	47992 KB	Output is correct
11	Correct	55 ms	47996 KB	Output is correct
12	Correct	48 ms	47992 KB	Output is correct
13	Correct	50 ms	47864 KB	Output is correct
14	Correct	49 ms	47960 KB	Output is correct
15	Correct	52 ms	47992 KB	Output is correct
16	Correct	49 ms	47864 KB	Output is correct
17	Correct	51 ms	47864 KB	Output is correct
18	Correct	52 ms	47864 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	47480 KB	Output is correct
2	Correct	47 ms	47616 KB	Output is correct
3	Correct	51 ms	47992 KB	Output is correct
4	Correct	53 ms	47992 KB	Output is correct
5	Correct	59 ms	47992 KB	Output is correct
6	Correct	55 ms	48060 KB	Output is correct
7	Correct	49 ms	47992 KB	Output is correct
8	Correct	51 ms	47992 KB	Output is correct
9	Correct	54 ms	48120 KB	Output is correct
10	Correct	50 ms	47992 KB	Output is correct
11	Correct	55 ms	47996 KB	Output is correct
12	Correct	48 ms	47992 KB	Output is correct
13	Correct	50 ms	47864 KB	Output is correct
14	Correct	49 ms	47960 KB	Output is correct
15	Correct	52 ms	47992 KB	Output is correct
16	Correct	49 ms	47864 KB	Output is correct
17	Correct	51 ms	47864 KB	Output is correct
18	Correct	52 ms	47864 KB	Output is correct
19	Correct	73 ms	49816 KB	Output is correct
20	Correct	81 ms	50184 KB	Output is correct
21	Correct	78 ms	50168 KB	Output is correct
22	Correct	78 ms	50168 KB	Output is correct
23	Correct	74 ms	49916 KB	Output is correct
24	Correct	75 ms	49884 KB	Output is correct
25	Correct	75 ms	49816 KB	Output is correct
26	Correct	78 ms	49780 KB	Output is correct
27	Correct	84 ms	49660 KB	Output is correct
28	Correct	72 ms	49656 KB	Output is correct

Subtask #3
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	59 ms	49144 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	47480 KB	Output is correct
2	Correct	47 ms	47616 KB	Output is correct
3	Correct	51 ms	47992 KB	Output is correct
4	Correct	53 ms	47992 KB	Output is correct
5	Correct	59 ms	47992 KB	Output is correct
6	Correct	55 ms	48060 KB	Output is correct
7	Correct	49 ms	47992 KB	Output is correct
8	Correct	51 ms	47992 KB	Output is correct
9	Correct	54 ms	48120 KB	Output is correct
10	Correct	50 ms	47992 KB	Output is correct
11	Correct	55 ms	47996 KB	Output is correct
12	Correct	48 ms	47992 KB	Output is correct
13	Correct	50 ms	47864 KB	Output is correct
14	Correct	49 ms	47960 KB	Output is correct
15	Correct	52 ms	47992 KB	Output is correct
16	Correct	49 ms	47864 KB	Output is correct
17	Correct	51 ms	47864 KB	Output is correct
18	Correct	52 ms	47864 KB	Output is correct
19	Correct	73 ms	49816 KB	Output is correct
20	Correct	81 ms	50184 KB	Output is correct
21	Correct	78 ms	50168 KB	Output is correct
22	Correct	78 ms	50168 KB	Output is correct
23	Correct	74 ms	49916 KB	Output is correct
24	Correct	75 ms	49884 KB	Output is correct
25	Correct	75 ms	49816 KB	Output is correct
26	Correct	78 ms	49780 KB	Output is correct
27	Correct	84 ms	49660 KB	Output is correct
28	Correct	72 ms	49656 KB	Output is correct
29	Incorrect	59 ms	49144 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

답안 #99759

Compilation message

Subtask #1 17.0 / 17.0

Subtask #2 21.0 / 21.0

Subtask #3 0 / 22.0

Subtask #4 0 / 40.0

Subtask #1
17.0 / 17.0

Subtask #2
21.0 / 21.0

Subtask #3
0 / 22.0

Subtask #4
0 / 40.0