oj.uz

Submission #412409

# Submission time Handle Problem Language Result Execution time Memory
412409 2021-05-26T20:19:01 Z nichke Bubble Sort 2 (JOI18_bubblesort2) C++14
38 / 100
 139 ms 52600 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxn = 1e6 + 100;
vector<int> a, pos, val, ans;

int timer;
map<int, int> mp;
set<int> ind[mxn];
int tree[4 * mxn], lazy[4 * mxn], lz[4 * mxn];

void push(int v, int l, int r) {
	if (r < l) return;
	if (lz[v] != 0) {
		tree[v] += lazy[v];
		if (l != r) {
			lz[2 * v + 1] = 1;
			lz[2 * v + 2] = 1;
			lazy[2 * v + 1] += lazy[v];
			lazy[2 * v + 2] += lazy[v];
		}
		lazy[v] = 0;
		lz[v] = 0;
	}
}

void update(int v, int tl, int tr, int ql, int qr, int val) {
	push(v, tl, tr);
	if (tl > tr || tl > qr || tr < ql) return;
	if (tl >= ql && tr <= qr) {
		lz[v] = 1;
		lazy[v] += val;
		push(v, tl, tr);
		return;
	}
	int tm = (tl + tr) / 2;
	update(2 * v + 1, tl, tm, ql, qr, val);
	update(2 * v + 2, tm + 1, tr, ql, qr, val);
	tree[v] = max(tree[2 * v + 1], tree[2 * v + 2]);
}

void rem(int v, int x) {
	update(0, 0, timer - 1, x, timer - 1, 1);
	if (v == *ind[x].rbegin()) {
		auto it = ind[x].rbegin();
		int val = -*it;
		it--;
		val += *it;
		update(0, 0, timer - 1, x, x, val);
	}
	ind[x].erase(v);
}

void add(int v, int x) {
	update(0, 0, timer - 1, x, timer - 1, -1);
	if (v > *ind[x].rbegin()) {
		update(0, 0, timer - 1, x, x, v - *ind[x].rbegin());
	}
	ind[x].insert(v);
	a[v] = x;
}

void solve() {
	for (auto it : a) mp[it] = 1;
	for (auto it : val) mp[it] = 1;
	for (auto &it : mp) {
		it.second = timer++;
	}
	for (int i = 0; i < timer; i++) {
		ind[i].insert(-mxn);
	}
	for (int i = 0; i < a.size(); i++) {
		a[i] = mp[a[i]];
		ind[a[i]].insert(i);
		update(0, 0, timer - 1, a[i], timer - 1, -1);
	}
	for (int i = 0; i < timer; i++) {
		update(0, 0, timer - 1, i, i, *ind[i].rbegin());
	}
	for (int q = 0; q < pos.size(); q++) {
		rem(pos[q], a[pos[q]]);
		add(pos[q], mp[val[q]]);
		ans.push_back(tree[0] + 1);
	}
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
	a = A;
	pos = X;
	val = V;
	solve();
	return ans;
}

Compilation message

bubblesort2.cpp: In function 'void solve()':
bubblesort2.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
bubblesort2.cpp:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for (int q = 0; q < pos.size(); q++) {
      |                  ~~^~~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47436 KB Output is correct
2 Correct 34 ms 47468 KB Output is correct
3 Correct 37 ms 47876 KB Output is correct
4 Correct 37 ms 47860 KB Output is correct
5 Correct 37 ms 47888 KB Output is correct
6 Correct 36 ms 47948 KB Output is correct
7 Correct 37 ms 47924 KB Output is correct
8 Correct 36 ms 47896 KB Output is correct
9 Correct 38 ms 47908 KB Output is correct
10 Correct 36 ms 47812 KB Output is correct
11 Correct 36 ms 47820 KB Output is correct
12 Correct 35 ms 47812 KB Output is correct
13 Correct 35 ms 47796 KB Output is correct
14 Correct 36 ms 47776 KB Output is correct
15 Correct 37 ms 47820 KB Output is correct
16 Correct 35 ms 47812 KB Output is correct
17 Correct 36 ms 47812 KB Output is correct
18 Correct 35 ms 47716 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47436 KB Output is correct
2 Correct 34 ms 47468 KB Output is correct
3 Correct 37 ms 47876 KB Output is correct
4 Correct 37 ms 47860 KB Output is correct
5 Correct 37 ms 47888 KB Output is correct
6 Correct 36 ms 47948 KB Output is correct
7 Correct 37 ms 47924 KB Output is correct
8 Correct 36 ms 47896 KB Output is correct
9 Correct 38 ms 47908 KB Output is correct
10 Correct 36 ms 47812 KB Output is correct
11 Correct 36 ms 47820 KB Output is correct
12 Correct 35 ms 47812 KB Output is correct
13 Correct 35 ms 47796 KB Output is correct
14 Correct 36 ms 47776 KB Output is correct
15 Correct 37 ms 47820 KB Output is correct
16 Correct 35 ms 47812 KB Output is correct
17 Correct 36 ms 47812 KB Output is correct
18 Correct 35 ms 47716 KB Output is correct
19 Correct 60 ms 49552 KB Output is correct
20 Correct 63 ms 49860 KB Output is correct
21 Correct 61 ms 49812 KB Output is correct
22 Correct 69 ms 49904 KB Output is correct
23 Correct 61 ms 49860 KB Output is correct
24 Correct 59 ms 49732 KB Output is correct
25 Correct 59 ms 49568 KB Output is correct
26 Correct 58 ms 49632 KB Output is correct
27 Correct 57 ms 49492 KB Output is correct
28 Correct 56 ms 49476 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 48932 KB Output is correct
2 Correct 83 ms 50460 KB Output is correct
3 Correct 120 ms 52480 KB Output is correct
4 Correct 121 ms 52440 KB Output is correct
5 Correct 116 ms 52388 KB Output is correct
6 Correct 122 ms 52600 KB Output is correct
7 Correct 134 ms 52424 KB Output is correct
8 Correct 139 ms 52400 KB Output is correct
9 Correct 118 ms 52424 KB Output is correct
10 Incorrect 103 ms 52544 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 47436 KB Output is correct
2 Correct 34 ms 47468 KB Output is correct
3 Correct 37 ms 47876 KB Output is correct
4 Correct 37 ms 47860 KB Output is correct
5 Correct 37 ms 47888 KB Output is correct
6 Correct 36 ms 47948 KB Output is correct
7 Correct 37 ms 47924 KB Output is correct
8 Correct 36 ms 47896 KB Output is correct
9 Correct 38 ms 47908 KB Output is correct
10 Correct 36 ms 47812 KB Output is correct
11 Correct 36 ms 47820 KB Output is correct
12 Correct 35 ms 47812 KB Output is correct
13 Correct 35 ms 47796 KB Output is correct
14 Correct 36 ms 47776 KB Output is correct
15 Correct 37 ms 47820 KB Output is correct
16 Correct 35 ms 47812 KB Output is correct
17 Correct 36 ms 47812 KB Output is correct
18 Correct 35 ms 47716 KB Output is correct
19 Correct 60 ms 49552 KB Output is correct
20 Correct 63 ms 49860 KB Output is correct
21 Correct 61 ms 49812 KB Output is correct
22 Correct 69 ms 49904 KB Output is correct
23 Correct 61 ms 49860 KB Output is correct
24 Correct 59 ms 49732 KB Output is correct
25 Correct 59 ms 49568 KB Output is correct
26 Correct 58 ms 49632 KB Output is correct
27 Correct 57 ms 49492 KB Output is correct
28 Correct 56 ms 49476 KB Output is correct
29 Correct 49 ms 48932 KB Output is correct
30 Correct 83 ms 50460 KB Output is correct
31 Correct 120 ms 52480 KB Output is correct
32 Correct 121 ms 52440 KB Output is correct
33 Correct 116 ms 52388 KB Output is correct
34 Correct 122 ms 52600 KB Output is correct
35 Correct 134 ms 52424 KB Output is correct
36 Correct 139 ms 52400 KB Output is correct
37 Correct 118 ms 52424 KB Output is correct
38 Incorrect 103 ms 52544 KB Output isn't correct
39 Halted 0 ms 0 KB -