oj.uz

Submission #813152

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

#define ll int64_t

const ll inf = 1e9;
const int N = 1e6 + 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);
	vector<int> cnt(n, 0);
	vector<ll> c(n);
	vector<ll> vals;
	//compresam coordonatele si ne asiguram sa nu avem duplicate
	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 * 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);
		ans[k] = 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, int64_t)':
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 242 ms 29124 KB Output is correct
2 Correct 216 ms 29036 KB Output is correct
3 Correct 219 ms 29272 KB Output is correct
4 Correct 234 ms 29284 KB Output is correct
5 Correct 217 ms 29216 KB Output is correct
6 Correct 283 ms 29256 KB Output is correct
7 Correct 238 ms 29384 KB Output is correct
8 Correct 242 ms 29260 KB Output is correct
9 Correct 224 ms 29260 KB Output is correct
10 Correct 278 ms 29248 KB Output is correct
11 Correct 217 ms 29256 KB Output is correct
12 Correct 223 ms 29216 KB Output is correct
13 Correct 317 ms 29224 KB Output is correct
14 Correct 219 ms 29208 KB Output is correct
15 Correct 274 ms 29188 KB Output is correct
16 Correct 219 ms 29276 KB Output is correct
17 Correct 217 ms 29260 KB Output is correct
18 Correct 221 ms 29168 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 29124 KB Output is correct
2 Correct 216 ms 29036 KB Output is correct
3 Correct 219 ms 29272 KB Output is correct
4 Correct 234 ms 29284 KB Output is correct
5 Correct 217 ms 29216 KB Output is correct
6 Correct 283 ms 29256 KB Output is correct
7 Correct 238 ms 29384 KB Output is correct
8 Correct 242 ms 29260 KB Output is correct
9 Correct 224 ms 29260 KB Output is correct
10 Correct 278 ms 29248 KB Output is correct
11 Correct 217 ms 29256 KB Output is correct
12 Correct 223 ms 29216 KB Output is correct
13 Correct 317 ms 29224 KB Output is correct
14 Correct 219 ms 29208 KB Output is correct
15 Correct 274 ms 29188 KB Output is correct
16 Correct 219 ms 29276 KB Output is correct
17 Correct 217 ms 29260 KB Output is correct
18 Correct 221 ms 29168 KB Output is correct
19 Correct 229 ms 29812 KB Output is correct
20 Correct 232 ms 29804 KB Output is correct
21 Correct 236 ms 29840 KB Output is correct
22 Correct 230 ms 29812 KB Output is correct
23 Correct 250 ms 29792 KB Output is correct
24 Correct 235 ms 30144 KB Output is correct
25 Correct 230 ms 29840 KB Output is correct
26 Correct 233 ms 29784 KB Output is correct
27 Correct 228 ms 29812 KB Output is correct
28 Correct 227 ms 29768 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 30152 KB Output is correct
2 Correct 277 ms 31444 KB Output is correct
3 Correct 345 ms 32832 KB Output is correct
4 Correct 333 ms 32924 KB Output is correct
5 Correct 326 ms 32932 KB Output is correct
6 Correct 331 ms 32816 KB Output is correct
7 Correct 341 ms 32832 KB Output is correct
8 Correct 336 ms 32920 KB Output is correct
9 Correct 349 ms 32824 KB Output is correct
10 Incorrect 306 ms 32732 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 242 ms 29124 KB Output is correct
2 Correct 216 ms 29036 KB Output is correct
3 Correct 219 ms 29272 KB Output is correct
4 Correct 234 ms 29284 KB Output is correct
5 Correct 217 ms 29216 KB Output is correct
6 Correct 283 ms 29256 KB Output is correct
7 Correct 238 ms 29384 KB Output is correct
8 Correct 242 ms 29260 KB Output is correct
9 Correct 224 ms 29260 KB Output is correct
10 Correct 278 ms 29248 KB Output is correct
11 Correct 217 ms 29256 KB Output is correct
12 Correct 223 ms 29216 KB Output is correct
13 Correct 317 ms 29224 KB Output is correct
14 Correct 219 ms 29208 KB Output is correct
15 Correct 274 ms 29188 KB Output is correct
16 Correct 219 ms 29276 KB Output is correct
17 Correct 217 ms 29260 KB Output is correct
18 Correct 221 ms 29168 KB Output is correct
19 Correct 229 ms 29812 KB Output is correct
20 Correct 232 ms 29804 KB Output is correct
21 Correct 236 ms 29840 KB Output is correct
22 Correct 230 ms 29812 KB Output is correct
23 Correct 250 ms 29792 KB Output is correct
24 Correct 235 ms 30144 KB Output is correct
25 Correct 230 ms 29840 KB Output is correct
26 Correct 233 ms 29784 KB Output is correct
27 Correct 228 ms 29812 KB Output is correct
28 Correct 227 ms 29768 KB Output is correct
29 Correct 238 ms 30152 KB Output is correct
30 Correct 277 ms 31444 KB Output is correct
31 Correct 345 ms 32832 KB Output is correct
32 Correct 333 ms 32924 KB Output is correct
33 Correct 326 ms 32932 KB Output is correct
34 Correct 331 ms 32816 KB Output is correct
35 Correct 341 ms 32832 KB Output is correct
36 Correct 336 ms 32920 KB Output is correct
37 Correct 349 ms 32824 KB Output is correct
38 Incorrect 306 ms 32732 KB Output isn't correct
39 Halted 0 ms 0 KB -