oj.uz

Submission #813153

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

#define ll int64_t

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);
	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 917 ms 115236 KB Output is correct
2 Correct 952 ms 115256 KB Output is correct
3 Correct 959 ms 115352 KB Output is correct
4 Correct 984 ms 115328 KB Output is correct
5 Correct 951 ms 115332 KB Output is correct
6 Correct 935 ms 115420 KB Output is correct
7 Correct 932 ms 115436 KB Output is correct
8 Correct 956 ms 115368 KB Output is correct
9 Correct 940 ms 115496 KB Output is correct
10 Correct 953 ms 115440 KB Output is correct
11 Correct 938 ms 115448 KB Output is correct
12 Correct 975 ms 115404 KB Output is correct
13 Correct 933 ms 115436 KB Output is correct
14 Correct 964 ms 115388 KB Output is correct
15 Correct 934 ms 115440 KB Output is correct
16 Correct 955 ms 115424 KB Output is correct
17 Correct 932 ms 115348 KB Output is correct
18 Correct 934 ms 115460 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 917 ms 115236 KB Output is correct
2 Correct 952 ms 115256 KB Output is correct
3 Correct 959 ms 115352 KB Output is correct
4 Correct 984 ms 115328 KB Output is correct
5 Correct 951 ms 115332 KB Output is correct
6 Correct 935 ms 115420 KB Output is correct
7 Correct 932 ms 115436 KB Output is correct
8 Correct 956 ms 115368 KB Output is correct
9 Correct 940 ms 115496 KB Output is correct
10 Correct 953 ms 115440 KB Output is correct
11 Correct 938 ms 115448 KB Output is correct
12 Correct 975 ms 115404 KB Output is correct
13 Correct 933 ms 115436 KB Output is correct
14 Correct 964 ms 115388 KB Output is correct
15 Correct 934 ms 115440 KB Output is correct
16 Correct 955 ms 115424 KB Output is correct
17 Correct 932 ms 115348 KB Output is correct
18 Correct 934 ms 115460 KB Output is correct
19 Correct 1008 ms 115852 KB Output is correct
20 Correct 955 ms 115920 KB Output is correct
21 Correct 972 ms 115896 KB Output is correct
22 Correct 953 ms 115840 KB Output is correct
23 Correct 948 ms 115896 KB Output is correct
24 Correct 945 ms 115956 KB Output is correct
25 Correct 943 ms 115824 KB Output is correct
26 Correct 933 ms 115948 KB Output is correct
27 Correct 948 ms 115824 KB Output is correct
28 Correct 937 ms 115904 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1012 ms 116324 KB Output is correct
2 Correct 1010 ms 117348 KB Output is correct
3 Correct 1049 ms 118600 KB Output is correct
4 Correct 1066 ms 118580 KB Output is correct
5 Correct 1042 ms 118616 KB Output is correct
6 Correct 1048 ms 118460 KB Output is correct
7 Correct 1041 ms 118644 KB Output is correct
8 Correct 1043 ms 118532 KB Output is correct
9 Correct 1046 ms 118520 KB Output is correct
10 Incorrect 1025 ms 118328 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 917 ms 115236 KB Output is correct
2 Correct 952 ms 115256 KB Output is correct
3 Correct 959 ms 115352 KB Output is correct
4 Correct 984 ms 115328 KB Output is correct
5 Correct 951 ms 115332 KB Output is correct
6 Correct 935 ms 115420 KB Output is correct
7 Correct 932 ms 115436 KB Output is correct
8 Correct 956 ms 115368 KB Output is correct
9 Correct 940 ms 115496 KB Output is correct
10 Correct 953 ms 115440 KB Output is correct
11 Correct 938 ms 115448 KB Output is correct
12 Correct 975 ms 115404 KB Output is correct
13 Correct 933 ms 115436 KB Output is correct
14 Correct 964 ms 115388 KB Output is correct
15 Correct 934 ms 115440 KB Output is correct
16 Correct 955 ms 115424 KB Output is correct
17 Correct 932 ms 115348 KB Output is correct
18 Correct 934 ms 115460 KB Output is correct
19 Correct 1008 ms 115852 KB Output is correct
20 Correct 955 ms 115920 KB Output is correct
21 Correct 972 ms 115896 KB Output is correct
22 Correct 953 ms 115840 KB Output is correct
23 Correct 948 ms 115896 KB Output is correct
24 Correct 945 ms 115956 KB Output is correct
25 Correct 943 ms 115824 KB Output is correct
26 Correct 933 ms 115948 KB Output is correct
27 Correct 948 ms 115824 KB Output is correct
28 Correct 937 ms 115904 KB Output is correct
29 Correct 1012 ms 116324 KB Output is correct
30 Correct 1010 ms 117348 KB Output is correct
31 Correct 1049 ms 118600 KB Output is correct
32 Correct 1066 ms 118580 KB Output is correct
33 Correct 1042 ms 118616 KB Output is correct
34 Correct 1048 ms 118460 KB Output is correct
35 Correct 1041 ms 118644 KB Output is correct
36 Correct 1043 ms 118532 KB Output is correct
37 Correct 1046 ms 118520 KB Output is correct
38 Incorrect 1025 ms 118328 KB Output isn't correct
39 Halted 0 ms 0 KB -