oj.uz

Submission #813188

# Submission time Handle Problem Language Result Execution time Memory
813188 2023-08-07T14:10:09 Z SlavicG Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 1282 ms 117944 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 < N; ++i) modif(1, 0, N - 1, i, 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 1024 ms 115280 KB Output is correct
2 Correct 1038 ms 115312 KB Output is correct
3 Correct 1077 ms 115436 KB Output is correct
4 Correct 1000 ms 115384 KB Output is correct
5 Correct 1025 ms 115348 KB Output is correct
6 Correct 997 ms 115328 KB Output is correct
7 Correct 1020 ms 115304 KB Output is correct
8 Correct 1060 ms 115388 KB Output is correct
9 Correct 1002 ms 115396 KB Output is correct
10 Correct 996 ms 115460 KB Output is correct
11 Correct 1000 ms 115340 KB Output is correct
12 Correct 1038 ms 115332 KB Output is correct
13 Correct 1033 ms 115432 KB Output is correct
14 Correct 1006 ms 115404 KB Output is correct
15 Correct 1000 ms 115392 KB Output is correct
16 Correct 997 ms 115396 KB Output is correct
17 Correct 1046 ms 115456 KB Output is correct
18 Correct 999 ms 115532 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1024 ms 115280 KB Output is correct
2 Correct 1038 ms 115312 KB Output is correct
3 Correct 1077 ms 115436 KB Output is correct
4 Correct 1000 ms 115384 KB Output is correct
5 Correct 1025 ms 115348 KB Output is correct
6 Correct 997 ms 115328 KB Output is correct
7 Correct 1020 ms 115304 KB Output is correct
8 Correct 1060 ms 115388 KB Output is correct
9 Correct 1002 ms 115396 KB Output is correct
10 Correct 996 ms 115460 KB Output is correct
11 Correct 1000 ms 115340 KB Output is correct
12 Correct 1038 ms 115332 KB Output is correct
13 Correct 1033 ms 115432 KB Output is correct
14 Correct 1006 ms 115404 KB Output is correct
15 Correct 1000 ms 115392 KB Output is correct
16 Correct 997 ms 115396 KB Output is correct
17 Correct 1046 ms 115456 KB Output is correct
18 Correct 999 ms 115532 KB Output is correct
19 Correct 1047 ms 115672 KB Output is correct
20 Correct 1033 ms 115776 KB Output is correct
21 Correct 1043 ms 115880 KB Output is correct
22 Correct 1072 ms 115816 KB Output is correct
23 Correct 1016 ms 115740 KB Output is correct
24 Correct 1104 ms 115732 KB Output is correct
25 Correct 1024 ms 115812 KB Output is correct
26 Correct 1068 ms 115752 KB Output is correct
27 Correct 1018 ms 115840 KB Output is correct
28 Correct 1056 ms 115728 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1031 ms 115956 KB Output is correct
2 Correct 1106 ms 116892 KB Output is correct
3 Correct 1157 ms 117916 KB Output is correct
4 Correct 1146 ms 117944 KB Output is correct
5 Correct 1138 ms 117884 KB Output is correct
6 Correct 1182 ms 117940 KB Output is correct
7 Correct 1259 ms 117904 KB Output is correct
8 Correct 1185 ms 117892 KB Output is correct
9 Correct 1282 ms 117856 KB Output is correct
10 Incorrect 1143 ms 117704 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1024 ms 115280 KB Output is correct
2 Correct 1038 ms 115312 KB Output is correct
3 Correct 1077 ms 115436 KB Output is correct
4 Correct 1000 ms 115384 KB Output is correct
5 Correct 1025 ms 115348 KB Output is correct
6 Correct 997 ms 115328 KB Output is correct
7 Correct 1020 ms 115304 KB Output is correct
8 Correct 1060 ms 115388 KB Output is correct
9 Correct 1002 ms 115396 KB Output is correct
10 Correct 996 ms 115460 KB Output is correct
11 Correct 1000 ms 115340 KB Output is correct
12 Correct 1038 ms 115332 KB Output is correct
13 Correct 1033 ms 115432 KB Output is correct
14 Correct 1006 ms 115404 KB Output is correct
15 Correct 1000 ms 115392 KB Output is correct
16 Correct 997 ms 115396 KB Output is correct
17 Correct 1046 ms 115456 KB Output is correct
18 Correct 999 ms 115532 KB Output is correct
19 Correct 1047 ms 115672 KB Output is correct
20 Correct 1033 ms 115776 KB Output is correct
21 Correct 1043 ms 115880 KB Output is correct
22 Correct 1072 ms 115816 KB Output is correct
23 Correct 1016 ms 115740 KB Output is correct
24 Correct 1104 ms 115732 KB Output is correct
25 Correct 1024 ms 115812 KB Output is correct
26 Correct 1068 ms 115752 KB Output is correct
27 Correct 1018 ms 115840 KB Output is correct
28 Correct 1056 ms 115728 KB Output is correct
29 Correct 1031 ms 115956 KB Output is correct
30 Correct 1106 ms 116892 KB Output is correct
31 Correct 1157 ms 117916 KB Output is correct
32 Correct 1146 ms 117944 KB Output is correct
33 Correct 1138 ms 117884 KB Output is correct
34 Correct 1182 ms 117940 KB Output is correct
35 Correct 1259 ms 117904 KB Output is correct
36 Correct 1185 ms 117892 KB Output is correct
37 Correct 1282 ms 117856 KB Output is correct
38 Incorrect 1143 ms 117704 KB Output isn't correct
39 Halted 0 ms 0 KB -