답안 #99761 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
99761	2019-03-06T22:54:13 Z	luciocf	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	92 ms	50012 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)
	{
		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 -1e9-10;
	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(1e9+10);

	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

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	47480 KB	Output is correct
2	Correct	45 ms	47616 KB	Output is correct
3	Correct	50 ms	47992 KB	Output is correct
4	Correct	57 ms	47992 KB	Output is correct
5	Correct	49 ms	47992 KB	Output is correct
6	Correct	51 ms	47992 KB	Output is correct
7	Correct	49 ms	48016 KB	Output is correct
8	Correct	47 ms	48016 KB	Output is correct
9	Correct	47 ms	47992 KB	Output is correct
10	Correct	49 ms	47992 KB	Output is correct
11	Correct	52 ms	47964 KB	Output is correct
12	Correct	52 ms	47992 KB	Output is correct
13	Correct	46 ms	47864 KB	Output is correct
14	Correct	48 ms	47864 KB	Output is correct
15	Correct	48 ms	47864 KB	Output is correct
16	Correct	51 ms	47872 KB	Output is correct
17	Correct	52 ms	47864 KB	Output is correct
18	Correct	50 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	45 ms	47616 KB	Output is correct
3	Correct	50 ms	47992 KB	Output is correct
4	Correct	57 ms	47992 KB	Output is correct
5	Correct	49 ms	47992 KB	Output is correct
6	Correct	51 ms	47992 KB	Output is correct
7	Correct	49 ms	48016 KB	Output is correct
8	Correct	47 ms	48016 KB	Output is correct
9	Correct	47 ms	47992 KB	Output is correct
10	Correct	49 ms	47992 KB	Output is correct
11	Correct	52 ms	47964 KB	Output is correct
12	Correct	52 ms	47992 KB	Output is correct
13	Correct	46 ms	47864 KB	Output is correct
14	Correct	48 ms	47864 KB	Output is correct
15	Correct	48 ms	47864 KB	Output is correct
16	Correct	51 ms	47872 KB	Output is correct
17	Correct	52 ms	47864 KB	Output is correct
18	Correct	50 ms	47864 KB	Output is correct
19	Correct	71 ms	49656 KB	Output is correct
20	Correct	83 ms	49912 KB	Output is correct
21	Correct	92 ms	49912 KB	Output is correct
22	Correct	83 ms	50012 KB	Output is correct
23	Correct	73 ms	49756 KB	Output is correct
24	Correct	74 ms	49784 KB	Output is correct
25	Correct	74 ms	49700 KB	Output is correct
26	Correct	72 ms	49672 KB	Output is correct
27	Correct	67 ms	49500 KB	Output is correct
28	Correct	68 ms	49528 KB	Output is correct

Subtask #3
0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	62 ms	49168 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	45 ms	47616 KB	Output is correct
3	Correct	50 ms	47992 KB	Output is correct
4	Correct	57 ms	47992 KB	Output is correct
5	Correct	49 ms	47992 KB	Output is correct
6	Correct	51 ms	47992 KB	Output is correct
7	Correct	49 ms	48016 KB	Output is correct
8	Correct	47 ms	48016 KB	Output is correct
9	Correct	47 ms	47992 KB	Output is correct
10	Correct	49 ms	47992 KB	Output is correct
11	Correct	52 ms	47964 KB	Output is correct
12	Correct	52 ms	47992 KB	Output is correct
13	Correct	46 ms	47864 KB	Output is correct
14	Correct	48 ms	47864 KB	Output is correct
15	Correct	48 ms	47864 KB	Output is correct
16	Correct	51 ms	47872 KB	Output is correct
17	Correct	52 ms	47864 KB	Output is correct
18	Correct	50 ms	47864 KB	Output is correct
19	Correct	71 ms	49656 KB	Output is correct
20	Correct	83 ms	49912 KB	Output is correct
21	Correct	92 ms	49912 KB	Output is correct
22	Correct	83 ms	50012 KB	Output is correct
23	Correct	73 ms	49756 KB	Output is correct
24	Correct	74 ms	49784 KB	Output is correct
25	Correct	74 ms	49700 KB	Output is correct
26	Correct	72 ms	49672 KB	Output is correct
27	Correct	67 ms	49500 KB	Output is correct
28	Correct	68 ms	49528 KB	Output is correct
29	Incorrect	62 ms	49168 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

답안 #99761

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