oj.uz

Submission #813196

# Submission time Handle Problem Language Result Execution time Memory
813196 2023-08-07T14:12:50 Z SlavicG Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 225 ms 129528 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long

const ll inf = 1e9;
const int N = 4e6 + 5;
ll t[4 * N], lazy[4 * N];
void push(int i, int l, int r) {
	if(!lazy[i]) return;
	t[i] += lazy[i];
	if(l != r) {
		lazy[2 * i] += lazy[i];
		lazy[2 * i + 1] += lazy[i];
	}
	lazy[i] = 0;
}
void modif(int i, int l, int r, int tl, int tr, ll val) {
	push(i, l, r);
	if(l > tr || r < tl) return;
	if(l >= tl && r <= tr) {
		lazy[i] += val;
		push(i, l,r);
		return;
	}
	int mid = l + r >> 1;
	modif(2 * i, l, mid, tl, tr, val);
	modif(2 * i + 1, mid + 1, r, tl, tr, val);
	t[i] = max(t[2 * i], t[2 * i + 1]);
}
std::vector<int> countScans(vector<int> a, vector<int> X, vector<int> V){
	int n = a.size();
	int q = X.size();
	vector<int> ans(q);
	//compresam coordonatele si ne asiguram sa nu avem duplicate
	vector<ll> vals;
	for(int i = 0; i < n; ++i) {
		vals.push_back(inf * (ll)a[i] + i); 
	}
	for(int k = 0; k < q; ++k) {
		int i = X[k];
		ll newval = inf * V[k] + i;
		vals.push_back(newval);
	}
	sort(vals.begin(), vals.end());
	vals.erase(unique(vals.begin(), vals.end()), vals.end());
	for(int i = 0; i < n; ++i) {
		a[i] = lower_bound(vals.begin(), vals.end(), (ll)a[i] * (ll)inf + i) - vals.begin();
	}
	for(int k = 0; k < q; ++k) {
		int i = X[k];
		ll newval = inf * (ll)V[k] + i;
		V[k] = lower_bound(vals.begin(), vals.end(), newval) - vals.begin();
	}


	//acum rezolvam problema dupa ce am compresat tot
	for(int i = 0; i < 4 * N; ++i) t[i] = -inf;

	for(int i = 0; i < n; ++i) {
		modif(1, 0, N - 1, a[i], a[i], inf + i);
	}
	for(int i = 0; i < n; ++i) {
		modif(1, 0, N - 1, a[i] + 1, N - 1, -1);
	}
	for(int k = 0; k < q; ++k) {
		int i = X[k], newval = V[k];
		modif(1, 0, N - 1, a[i] + 1, N - 1, +1);
		modif(1, 0, N - 1, a[i], a[i], -2 * inf - i);
		a[i] = newval;
		modif(1, 0, N - 1, a[i], a[i], inf + i);
		modif(1, 0, N - 1, a[i] + 1, N - 1, -1);
		push(1, 0, N - 1);
		ans[k] = (int)max(0LL, t[1]); 
	}


	return ans;
}
/*
4 2
1 2 3 4
0 3
2 1
*/

Compilation message

bubblesort2.cpp: In function 'void modif(int, int, int, int, int, long long int)':
bubblesort2.cpp:27:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 125660 KB Output is correct
2 Correct 44 ms 125572 KB Output is correct
3 Correct 46 ms 125788 KB Output is correct
4 Correct 48 ms 125736 KB Output is correct
5 Correct 47 ms 125776 KB Output is correct
6 Correct 47 ms 125768 KB Output is correct
7 Correct 47 ms 125716 KB Output is correct
8 Correct 47 ms 125708 KB Output is correct
9 Correct 48 ms 125668 KB Output is correct
10 Correct 47 ms 125724 KB Output is correct
11 Correct 47 ms 125756 KB Output is correct
12 Correct 47 ms 125688 KB Output is correct
13 Correct 48 ms 125772 KB Output is correct
14 Correct 54 ms 125716 KB Output is correct
15 Correct 55 ms 125708 KB Output is correct
16 Correct 55 ms 125712 KB Output is correct
17 Correct 47 ms 125672 KB Output is correct
18 Correct 47 ms 125676 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 125660 KB Output is correct
2 Correct 44 ms 125572 KB Output is correct
3 Correct 46 ms 125788 KB Output is correct
4 Correct 48 ms 125736 KB Output is correct
5 Correct 47 ms 125776 KB Output is correct
6 Correct 47 ms 125768 KB Output is correct
7 Correct 47 ms 125716 KB Output is correct
8 Correct 47 ms 125708 KB Output is correct
9 Correct 48 ms 125668 KB Output is correct
10 Correct 47 ms 125724 KB Output is correct
11 Correct 47 ms 125756 KB Output is correct
12 Correct 47 ms 125688 KB Output is correct
13 Correct 48 ms 125772 KB Output is correct
14 Correct 54 ms 125716 KB Output is correct
15 Correct 55 ms 125708 KB Output is correct
16 Correct 55 ms 125712 KB Output is correct
17 Correct 47 ms 125672 KB Output is correct
18 Correct 47 ms 125676 KB Output is correct
19 Correct 59 ms 126220 KB Output is correct
20 Correct 70 ms 126316 KB Output is correct
21 Correct 62 ms 126320 KB Output is correct
22 Correct 64 ms 126312 KB Output is correct
23 Correct 62 ms 126224 KB Output is correct
24 Correct 74 ms 126228 KB Output is correct
25 Correct 76 ms 126268 KB Output is correct
26 Correct 59 ms 126264 KB Output is correct
27 Correct 76 ms 126156 KB Output is correct
28 Correct 74 ms 126240 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 126608 KB Output is correct
2 Correct 192 ms 128076 KB Output is correct
3 Correct 225 ms 129528 KB Output is correct
4 Correct 174 ms 129524 KB Output is correct
5 Correct 173 ms 129484 KB Output is correct
6 Correct 199 ms 129484 KB Output is correct
7 Correct 204 ms 129488 KB Output is correct
8 Correct 191 ms 129488 KB Output is correct
9 Correct 194 ms 129496 KB Output is correct
10 Incorrect 155 ms 128688 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 125660 KB Output is correct
2 Correct 44 ms 125572 KB Output is correct
3 Correct 46 ms 125788 KB Output is correct
4 Correct 48 ms 125736 KB Output is correct
5 Correct 47 ms 125776 KB Output is correct
6 Correct 47 ms 125768 KB Output is correct
7 Correct 47 ms 125716 KB Output is correct
8 Correct 47 ms 125708 KB Output is correct
9 Correct 48 ms 125668 KB Output is correct
10 Correct 47 ms 125724 KB Output is correct
11 Correct 47 ms 125756 KB Output is correct
12 Correct 47 ms 125688 KB Output is correct
13 Correct 48 ms 125772 KB Output is correct
14 Correct 54 ms 125716 KB Output is correct
15 Correct 55 ms 125708 KB Output is correct
16 Correct 55 ms 125712 KB Output is correct
17 Correct 47 ms 125672 KB Output is correct
18 Correct 47 ms 125676 KB Output is correct
19 Correct 59 ms 126220 KB Output is correct
20 Correct 70 ms 126316 KB Output is correct
21 Correct 62 ms 126320 KB Output is correct
22 Correct 64 ms 126312 KB Output is correct
23 Correct 62 ms 126224 KB Output is correct
24 Correct 74 ms 126228 KB Output is correct
25 Correct 76 ms 126268 KB Output is correct
26 Correct 59 ms 126264 KB Output is correct
27 Correct 76 ms 126156 KB Output is correct
28 Correct 74 ms 126240 KB Output is correct
29 Correct 77 ms 126608 KB Output is correct
30 Correct 192 ms 128076 KB Output is correct
31 Correct 225 ms 129528 KB Output is correct
32 Correct 174 ms 129524 KB Output is correct
33 Correct 173 ms 129484 KB Output is correct
34 Correct 199 ms 129484 KB Output is correct
35 Correct 204 ms 129488 KB Output is correct
36 Correct 191 ms 129488 KB Output is correct
37 Correct 194 ms 129496 KB Output is correct
38 Incorrect 155 ms 128688 KB Output isn't correct
39 Halted 0 ms 0 KB -