답안 #776909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776909	2023-07-08T11:41:07 Z	PanosPask	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	32 ms	4488 KB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct SegTree {
	const ll NO_OP = 0;
	const ll NEUTRAL = 0;

	int size;
	vector<ll> tree;
	vector<ll> operations;

	void init(int n) {
		size = 1;
		while (size < n)
			size *= 2;

		tree.resize(2 * size, NEUTRAL);
		operations.assign(2 * size, NO_OP);
	}

	void propagate(int x) {
		tree[2 * x + 1] += operations[x];
		tree[2 * x + 2] += operations[x];
		operations[2 * x + 1] += operations[x];
		operations[2 * x + 2] += operations[x];

		operations[x] = NO_OP;
	}

	void modify(int l, int r, int v, int x, int lx, int rx) {
		if (l >= rx || lx >= r) {
			return;
		}
		else if (l <= lx && rx <= r) {
			tree[x] += v;
			operations[x] += v;
			return;
		}

		propagate(x);

		int mid = (lx + rx) / 2;
		modify(l, r, v, 2 * x + 1, lx, mid);
		modify(l, r, v, 2 * x + 2, mid, rx);

		tree[x] = max(tree[2 * x + 1], tree[2 * x +2]);
	}
	void modify(int l, int r, int v) {
		modify(l, r, v, 0, 0, size);
	}

	ll calc(int l, int r, int x, int lx, int rx) {
		if (l >= rx || lx >= r) {
			return NEUTRAL;
		}
		else if (l <= lx && rx <= r) {
			return tree[x];
		}

		propagate(x);

		int mid = (lx + rx) / 2;
		ll c1 = calc(l, r, 2 * x + 1, lx, mid);
		ll c2 = calc(l, r, 2 * x + 2, mid, rx);

		return max(c1, c2);
	}
	ll calc(int l, int r) {
		return max(calc(l, r, 0, 0, size), 0ll);
	}
};

int N;
set<int> seen;
vector<set<int>> latest;
unordered_map<int, int> compress;
vector<int> startv;

SegTree st;

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
	// Coordinate compression
	for (int i = 0; i < A.size(); i++)
		seen.insert(A[i]);
	for (int i = 0; i < V.size(); i++)
		seen.insert(V[i]);
	for (auto val : seen)
		compress[val] = N++;

	latest.resize(N);
	st.init(N);
	for (int val = 0; val < N; val++)
		latest[val].insert(-1);
	for (int i = 0; i < A.size(); i++) {
		A[i] = compress[A[i]];
		latest[A[i]].insert(i);

		st.modify(A[i] + 1, N, -1);
	}

	for (int val = 0; val < N; val++) {
		st.modify(val, val + 1, *latest[val].rbegin());
	}

	vector<int> ans;
	for (int q = 0; q < X.size(); q++) {
		int i = X[q];
		int val = compress[V[q]];
		int prev = A[i];

		// Take care of the old value first
		st.modify(prev + 1, N, +1);
		st.modify(prev, prev + 1, - *latest[prev].rbegin());
		latest[prev].erase(i);
		st.modify(prev, prev + 1, *latest[prev].rbegin());

		// Proccess the new value
		st.modify(val + 1, N, -1);
		st.modify(val, val + 1, - *latest[val].rbegin());
		latest[val].insert(i);
		st.modify(val, val + 1, *latest[val].rbegin());

		A[i] = val;
		ans.push_back(st.calc(0, N));
	}

	return ans;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for (int i = 0; i < A.size(); i++)
      |                  ~~^~~~~~~~~~
bubblesort2.cpp:90:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for (int i = 0; i < V.size(); i++)
      |                  ~~^~~~~~~~~~
bubblesort2.cpp:99:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for (int i = 0; i < A.size(); i++) {
      |                  ~~^~~~~~~~~~
bubblesort2.cpp:111:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |  for (int q = 0; q < X.size(); q++) {
      |                  ~~^~~~~~~~~~

Subtask #1
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	596 KB	Output is correct
2	Correct	3 ms	724 KB	Output is correct
3	Correct	7 ms	1276 KB	Output is correct
4	Correct	7 ms	1204 KB	Output is correct
5	Correct	6 ms	1236 KB	Output is correct
6	Correct	7 ms	1236 KB	Output is correct
7	Correct	6 ms	1236 KB	Output is correct
8	Correct	6 ms	1236 KB	Output is correct
9	Correct	6 ms	1236 KB	Output is correct
10	Correct	6 ms	1236 KB	Output is correct
11	Correct	6 ms	1236 KB	Output is correct
12	Correct	6 ms	1236 KB	Output is correct
13	Correct	6 ms	1108 KB	Output is correct
14	Correct	6 ms	1108 KB	Output is correct
15	Correct	5 ms	1108 KB	Output is correct
16	Correct	6 ms	1136 KB	Output is correct
17	Correct	5 ms	1108 KB	Output is correct
18	Correct	5 ms	1108 KB	Output is correct

Subtask #2
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	596 KB	Output is correct
2	Correct	3 ms	724 KB	Output is correct
3	Correct	7 ms	1276 KB	Output is correct
4	Correct	7 ms	1204 KB	Output is correct
5	Correct	6 ms	1236 KB	Output is correct
6	Correct	7 ms	1236 KB	Output is correct
7	Correct	6 ms	1236 KB	Output is correct
8	Correct	6 ms	1236 KB	Output is correct
9	Correct	6 ms	1236 KB	Output is correct
10	Correct	6 ms	1236 KB	Output is correct
11	Correct	6 ms	1236 KB	Output is correct
12	Correct	6 ms	1236 KB	Output is correct
13	Correct	6 ms	1108 KB	Output is correct
14	Correct	6 ms	1108 KB	Output is correct
15	Correct	5 ms	1108 KB	Output is correct
16	Correct	6 ms	1136 KB	Output is correct
17	Correct	5 ms	1108 KB	Output is correct
18	Correct	5 ms	1108 KB	Output is correct
19	Correct	25 ms	3944 KB	Output is correct
20	Correct	31 ms	4488 KB	Output is correct
21	Correct	32 ms	4308 KB	Output is correct
22	Correct	27 ms	4340 KB	Output is correct
23	Correct	26 ms	4052 KB	Output is correct
24	Correct	27 ms	3996 KB	Output is correct
25	Correct	30 ms	3816 KB	Output is correct
26	Correct	24 ms	3792 KB	Output is correct
27	Correct	24 ms	3668 KB	Output is correct
28	Correct	24 ms	3652 KB	Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	596 KB	Output is correct
2	Correct	3 ms	724 KB	Output is correct
3	Correct	7 ms	1276 KB	Output is correct
4	Correct	7 ms	1204 KB	Output is correct
5	Correct	6 ms	1236 KB	Output is correct
6	Correct	7 ms	1236 KB	Output is correct
7	Correct	6 ms	1236 KB	Output is correct
8	Correct	6 ms	1236 KB	Output is correct
9	Correct	6 ms	1236 KB	Output is correct
10	Correct	6 ms	1236 KB	Output is correct
11	Correct	6 ms	1236 KB	Output is correct
12	Correct	6 ms	1236 KB	Output is correct
13	Correct	6 ms	1108 KB	Output is correct
14	Correct	6 ms	1108 KB	Output is correct
15	Correct	5 ms	1108 KB	Output is correct
16	Correct	6 ms	1136 KB	Output is correct
17	Correct	5 ms	1108 KB	Output is correct
18	Correct	5 ms	1108 KB	Output is correct
19	Correct	25 ms	3944 KB	Output is correct
20	Correct	31 ms	4488 KB	Output is correct
21	Correct	32 ms	4308 KB	Output is correct
22	Correct	27 ms	4340 KB	Output is correct
23	Correct	26 ms	4052 KB	Output is correct
24	Correct	27 ms	3996 KB	Output is correct
25	Correct	30 ms	3816 KB	Output is correct
26	Correct	24 ms	3792 KB	Output is correct
27	Correct	24 ms	3668 KB	Output is correct
28	Correct	24 ms	3652 KB	Output is correct
29	Incorrect	13 ms	1816 KB	Output isn't correct
30	Halted	0 ms	0 KB	-

답안 #776909

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