oj.uz

Submission #398726

# Submission time Handle Problem Language Result Execution time Memory
398726 2021-05-04T18:49:09 Z nikatamliani Bubble Sort 2 (JOI18_bubblesort2) C++14
60 / 100
 3358 ms 193556 KB 
#include "bits/stdc++.h"
#include "bubblesort2.h"
using namespace std;
template <typename T>
struct segment_tree {
	vector<T> tree;
	vector<T> lazy;
	T neutral;
	function<T(T, T)> join;
	int size;
	segment_tree() {}
	segment_tree(int _size, T _neutral, function<T(T, T)> f) {
		join = f;
		size = _size;
		neutral = _neutral;
		tree = vector<T>(4 * size, neutral);
		lazy = vector<T>(4 * size);
	}
	
	void prop(int l, int r, int p) {
		if(lazy[p] == 0) return;
		if(l < r) {
			lazy[p << 1] += lazy[p];
			lazy[p << 1 | 1] += lazy[p];
		}
		tree[p] += lazy[p];
		lazy[p] = 0;
	}
	
	void point_update(int id, T val) {
		point_update(1, size, id, val, 1); 
	}
	
	void point_update(int l, int r, int x, T val, int p) {
		prop(l, r, p);
		if(l > x || r < x) {
			return;
		}
		if(l == r) {
			tree[p] = val;
			return;
		}
		int middle = l + r >> 1;
		point_update(l, middle, x, val, p << 1);
		point_update(middle+1, r, x, val, p << 1 | 1);
		tree[p] = join(tree[p << 1], tree[p << 1 | 1]);
	}
	
	void range_add(int L, int R, T val) {
		if(L > R) {
			return;
		}
		range_add(1, size, L, R, val, 1);
	}
	
	void range_add(int l, int r, int L, int R, T val, int p) {
		prop(l, r, p);
		if(L > r || l > R) return;
		if(L <= l && R >= r) {
			lazy[p] += val;
			prop(l, r, p);
			return;
		}
		int middle = l + r >> 1; 
		range_add(l, middle, L, R, val, p << 1);
		range_add(middle+1, r, L, R, val, p << 1 | 1); 
		tree[p] = join(tree[p << 1], tree[p << 1 |1]);
	}
	
	T get(int id) {
		return query(id, id);
	}
	
	T query(int L, int R) {
		if(L > R) {
			return neutral;
		}
		return query(1, size, L, R, 1); 
	}
	
	T query(int l, int r, int L, int R, int p) {
		prop(l, r, p); 
		if(L > r || l > R) return neutral;
		if(L <= l && R >= r) return tree[p];
		int middle = l + r >> 1;
		T lft = query(l, middle, L, R, p << 1);
		T rgh = query(middle+1, r, L, R, p << 1 | 1);
		return join(lft, rgh);
	}
};
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	int Q = (int)X.size(), N = (int)A.size();
	vector<int> answer(Q);
	vector<array<int, 4>> coords;
	for(int i = 0; i < N; ++i) {
		coords.push_back({A[i], i, i, 0});
	}
	for(int i = 0; i < Q; ++i) {
		coords.push_back({V[i], X[i], i, 1});
	}
	sort(coords.begin(), coords.end());
	for(int i = 0; i < (int)coords.size(); ++i) {
		if(coords[i][3] == 0) {
			A[coords[i][2]] = i+1;
		} else {
			V[coords[i][2]] = i+1;
		}
	}
	segment_tree<int> t(N + Q, -1e9, [](int x, int y) -> int {
		return x > y ? x : y;
	});
	segment_tree<int> bruh(N + Q, 0, [](int x, int y) -> int {
		return x+y;
	});
	vector<int> id(N + Q);
	for(int i = 0; i < N; ++i) {
		id[A[i]] = i;
	}
	vector<int> save_A = A;
	sort(A.begin(), A.end());
	for(int i = 0; i < N; ++i) {
		t.point_update(A[i], id[A[i]] - i);
		bruh.point_update(A[i], 1); 
	}
	A = save_A;
	for(int i = 0; i < Q; ++i) {
		int prv = A[X[i]];
		int nxt = V[i];
		A[X[i]] = V[i];
		id[nxt] = id[prv];
		bruh.point_update(prv, 0);
		bruh.point_update(nxt, 1);
		if(nxt > prv) {
			t.range_add(prv, nxt, 1);
			t.point_update(nxt, id[nxt] - bruh.query(1, nxt-1));
		} else {
			t.range_add(nxt, prv, -1);
			t.point_update(nxt, id[nxt] - bruh.query(1, nxt-1));
		}
		t.point_update(prv, -1e9);
		answer[i] = t.query(1, N + Q);
	}
	return answer;
}

Compilation message

bubblesort2.cpp: In instantiation of 'void segment_tree<T>::point_update(int, int, int, T, int) [with T = int]':
bubblesort2.cpp:31:3:   required from 'void segment_tree<T>::point_update(int, T) [with T = int]'
bubblesort2.cpp:122:36:   required from here
bubblesort2.cpp:43:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int middle = l + r >> 1;
      |                ~~^~~
bubblesort2.cpp: In instantiation of 'void segment_tree<T>::range_add(int, int, int, int, T, int) [with T = int]':
bubblesort2.cpp:53:3:   required from 'void segment_tree<T>::range_add(int, int, T) [with T = int]'
bubblesort2.cpp:134:27:   required from here
bubblesort2.cpp:64:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |   int middle = l + r >> 1;
      |                ~~^~~
bubblesort2.cpp: In instantiation of 'T segment_tree<T>::query(int, int, int, int, int) [with T = int]':
bubblesort2.cpp:78:32:   required from 'T segment_tree<T>::query(int, int) [with T = int]'
bubblesort2.cpp:135:53:   required from here
bubblesort2.cpp:85:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |   int middle = l + r >> 1;
      |                ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 592 KB Output is correct
3 Correct 7 ms 736 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 7 ms 716 KB Output is correct
7 Correct 7 ms 716 KB Output is correct
8 Correct 7 ms 772 KB Output is correct
9 Correct 7 ms 772 KB Output is correct
10 Correct 7 ms 716 KB Output is correct
11 Correct 7 ms 696 KB Output is correct
12 Correct 7 ms 772 KB Output is correct
13 Correct 7 ms 716 KB Output is correct
14 Correct 7 ms 700 KB Output is correct
15 Correct 7 ms 700 KB Output is correct
16 Correct 7 ms 688 KB Output is correct
17 Correct 7 ms 708 KB Output is correct
18 Correct 7 ms 768 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 592 KB Output is correct
3 Correct 7 ms 736 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 7 ms 716 KB Output is correct
7 Correct 7 ms 716 KB Output is correct
8 Correct 7 ms 772 KB Output is correct
9 Correct 7 ms 772 KB Output is correct
10 Correct 7 ms 716 KB Output is correct
11 Correct 7 ms 696 KB Output is correct
12 Correct 7 ms 772 KB Output is correct
13 Correct 7 ms 716 KB Output is correct
14 Correct 7 ms 700 KB Output is correct
15 Correct 7 ms 700 KB Output is correct
16 Correct 7 ms 688 KB Output is correct
17 Correct 7 ms 708 KB Output is correct
18 Correct 7 ms 768 KB Output is correct
19 Correct 27 ms 1816 KB Output is correct
20 Correct 31 ms 2116 KB Output is correct
21 Correct 31 ms 1992 KB Output is correct
22 Correct 31 ms 1992 KB Output is correct
23 Correct 30 ms 2080 KB Output is correct
24 Correct 30 ms 1992 KB Output is correct
25 Correct 29 ms 2080 KB Output is correct
26 Correct 29 ms 1968 KB Output is correct
27 Correct 28 ms 1992 KB Output is correct
28 Correct 30 ms 2080 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3144 KB Output is correct
2 Correct 122 ms 6760 KB Output is correct
3 Correct 248 ms 10572 KB Output is correct
4 Correct 243 ms 10652 KB Output is correct
5 Correct 235 ms 10664 KB Output is correct
6 Correct 229 ms 10612 KB Output is correct
7 Correct 231 ms 10552 KB Output is correct
8 Correct 232 ms 10600 KB Output is correct
9 Correct 231 ms 10548 KB Output is correct
10 Correct 209 ms 10700 KB Output is correct
11 Correct 201 ms 10740 KB Output is correct
12 Correct 201 ms 10684 KB Output is correct
13 Correct 206 ms 10800 KB Output is correct
14 Correct 205 ms 10728 KB Output is correct
15 Correct 207 ms 10716 KB Output is correct
16 Correct 209 ms 10648 KB Output is correct
17 Correct 210 ms 10676 KB Output is correct
18 Correct 204 ms 10724 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 332 KB Output is correct
2 Correct 3 ms 592 KB Output is correct
3 Correct 7 ms 736 KB Output is correct
4 Correct 7 ms 716 KB Output is correct
5 Correct 7 ms 716 KB Output is correct
6 Correct 7 ms 716 KB Output is correct
7 Correct 7 ms 716 KB Output is correct
8 Correct 7 ms 772 KB Output is correct
9 Correct 7 ms 772 KB Output is correct
10 Correct 7 ms 716 KB Output is correct
11 Correct 7 ms 696 KB Output is correct
12 Correct 7 ms 772 KB Output is correct
13 Correct 7 ms 716 KB Output is correct
14 Correct 7 ms 700 KB Output is correct
15 Correct 7 ms 700 KB Output is correct
16 Correct 7 ms 688 KB Output is correct
17 Correct 7 ms 708 KB Output is correct
18 Correct 7 ms 768 KB Output is correct
19 Correct 27 ms 1816 KB Output is correct
20 Correct 31 ms 2116 KB Output is correct
21 Correct 31 ms 1992 KB Output is correct
22 Correct 31 ms 1992 KB Output is correct
23 Correct 30 ms 2080 KB Output is correct
24 Correct 30 ms 1992 KB Output is correct
25 Correct 29 ms 2080 KB Output is correct
26 Correct 29 ms 1968 KB Output is correct
27 Correct 28 ms 1992 KB Output is correct
28 Correct 30 ms 2080 KB Output is correct
29 Correct 34 ms 3144 KB Output is correct
30 Correct 122 ms 6760 KB Output is correct
31 Correct 248 ms 10572 KB Output is correct
32 Correct 243 ms 10652 KB Output is correct
33 Correct 235 ms 10664 KB Output is correct
34 Correct 229 ms 10612 KB Output is correct
35 Correct 231 ms 10552 KB Output is correct
36 Correct 232 ms 10600 KB Output is correct
37 Correct 231 ms 10548 KB Output is correct
38 Correct 209 ms 10700 KB Output is correct
39 Correct 201 ms 10740 KB Output is correct
40 Correct 201 ms 10684 KB Output is correct
41 Correct 206 ms 10800 KB Output is correct
42 Correct 205 ms 10728 KB Output is correct
43 Correct 207 ms 10716 KB Output is correct
44 Correct 209 ms 10648 KB Output is correct
45 Correct 210 ms 10676 KB Output is correct
46 Correct 204 ms 10724 KB Output is correct
47 Correct 837 ms 33040 KB Output is correct
48 Runtime error 3358 ms 193556 KB Execution killed with signal 11
49 Halted 0 ms 0 KB -