oj.uz

Submission #813163

# Submission time Handle Problem Language Result Execution time Memory
813163 2023-08-07T14:02:13 Z SlavicG Bubble Sort 2 (JOI18_bubblesort2) C++17
38 / 100
 1330 ms 117968 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);
	//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] = 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 993 ms 115292 KB Output is correct
2 Correct 1050 ms 115324 KB Output is correct
3 Correct 1002 ms 115368 KB Output is correct
4 Correct 992 ms 115388 KB Output is correct
5 Correct 1018 ms 115372 KB Output is correct
6 Correct 996 ms 115344 KB Output is correct
7 Correct 1026 ms 115380 KB Output is correct
8 Correct 1014 ms 115300 KB Output is correct
9 Correct 1032 ms 115372 KB Output is correct
10 Correct 1012 ms 115420 KB Output is correct
11 Correct 994 ms 115520 KB Output is correct
12 Correct 1000 ms 115392 KB Output is correct
13 Correct 1038 ms 115372 KB Output is correct
14 Correct 1004 ms 115420 KB Output is correct
15 Correct 1010 ms 115352 KB Output is correct
16 Correct 1030 ms 115356 KB Output is correct
17 Correct 996 ms 115336 KB Output is correct
18 Correct 1016 ms 115308 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 993 ms 115292 KB Output is correct
2 Correct 1050 ms 115324 KB Output is correct
3 Correct 1002 ms 115368 KB Output is correct
4 Correct 992 ms 115388 KB Output is correct
5 Correct 1018 ms 115372 KB Output is correct
6 Correct 996 ms 115344 KB Output is correct
7 Correct 1026 ms 115380 KB Output is correct
8 Correct 1014 ms 115300 KB Output is correct
9 Correct 1032 ms 115372 KB Output is correct
10 Correct 1012 ms 115420 KB Output is correct
11 Correct 994 ms 115520 KB Output is correct
12 Correct 1000 ms 115392 KB Output is correct
13 Correct 1038 ms 115372 KB Output is correct
14 Correct 1004 ms 115420 KB Output is correct
15 Correct 1010 ms 115352 KB Output is correct
16 Correct 1030 ms 115356 KB Output is correct
17 Correct 996 ms 115336 KB Output is correct
18 Correct 1016 ms 115308 KB Output is correct
19 Correct 1004 ms 115844 KB Output is correct
20 Correct 1006 ms 115812 KB Output is correct
21 Correct 1012 ms 115824 KB Output is correct
22 Correct 1076 ms 115764 KB Output is correct
23 Correct 1068 ms 115808 KB Output is correct
24 Correct 1069 ms 115792 KB Output is correct
25 Correct 1080 ms 115712 KB Output is correct
26 Correct 1042 ms 115776 KB Output is correct
27 Correct 1037 ms 115744 KB Output is correct
28 Correct 1091 ms 115824 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1072 ms 116008 KB Output is correct
2 Correct 1140 ms 116888 KB Output is correct
3 Correct 1149 ms 117888 KB Output is correct
4 Correct 1135 ms 117924 KB Output is correct
5 Correct 1141 ms 117912 KB Output is correct
6 Correct 1330 ms 117968 KB Output is correct
7 Correct 1162 ms 117928 KB Output is correct
8 Correct 1212 ms 117916 KB Output is correct
9 Correct 1180 ms 117936 KB Output is correct
10 Incorrect 1134 ms 117732 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 993 ms 115292 KB Output is correct
2 Correct 1050 ms 115324 KB Output is correct
3 Correct 1002 ms 115368 KB Output is correct
4 Correct 992 ms 115388 KB Output is correct
5 Correct 1018 ms 115372 KB Output is correct
6 Correct 996 ms 115344 KB Output is correct
7 Correct 1026 ms 115380 KB Output is correct
8 Correct 1014 ms 115300 KB Output is correct
9 Correct 1032 ms 115372 KB Output is correct
10 Correct 1012 ms 115420 KB Output is correct
11 Correct 994 ms 115520 KB Output is correct
12 Correct 1000 ms 115392 KB Output is correct
13 Correct 1038 ms 115372 KB Output is correct
14 Correct 1004 ms 115420 KB Output is correct
15 Correct 1010 ms 115352 KB Output is correct
16 Correct 1030 ms 115356 KB Output is correct
17 Correct 996 ms 115336 KB Output is correct
18 Correct 1016 ms 115308 KB Output is correct
19 Correct 1004 ms 115844 KB Output is correct
20 Correct 1006 ms 115812 KB Output is correct
21 Correct 1012 ms 115824 KB Output is correct
22 Correct 1076 ms 115764 KB Output is correct
23 Correct 1068 ms 115808 KB Output is correct
24 Correct 1069 ms 115792 KB Output is correct
25 Correct 1080 ms 115712 KB Output is correct
26 Correct 1042 ms 115776 KB Output is correct
27 Correct 1037 ms 115744 KB Output is correct
28 Correct 1091 ms 115824 KB Output is correct
29 Correct 1072 ms 116008 KB Output is correct
30 Correct 1140 ms 116888 KB Output is correct
31 Correct 1149 ms 117888 KB Output is correct
32 Correct 1135 ms 117924 KB Output is correct
33 Correct 1141 ms 117912 KB Output is correct
34 Correct 1330 ms 117968 KB Output is correct
35 Correct 1162 ms 117928 KB Output is correct
36 Correct 1212 ms 117916 KB Output is correct
37 Correct 1180 ms 117936 KB Output is correct
38 Incorrect 1134 ms 117732 KB Output isn't correct
39 Halted 0 ms 0 KB -