#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
#define ll long long
const int base = 1<<20;
const ll INF = 1e18+7;
const ll MAXN = 1e6+7;
ll tree[base<<1];
ll lazy[base<<1];
void push(ll v){
lazy[2*v] += lazy[v];
lazy[2*v+1] += lazy[v];
tree[2*v] += lazy[v];
tree[2*v+1] += lazy[v];
lazy[v] = 0;
}
ll p, k;
ll val;
void update(ll v, ll l, ll r){
if(l > k || r < p) return;
if(p <= l && r <= k){
tree[v] += val;
lazy[v] += val;
}
else{
ll mid = (l+r)/2;
push(v);
update(2*v, l, mid);
update(2*v+1, mid+1, r);
tree[v] = max(tree[2*v], tree[2*v+1]);
}
}
ll query(ll v, ll l, ll r){
if(l > k || r < p) return -INF;
if(p <= l && r <= k){
return tree[v];
}
else{
ll mid = (l+r)/2;
push(v);
auto lQ = query(2*v, l, mid);
auto rQ = query(2*v+1, mid+1, r);
return max(lQ, rQ);
}
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
int n = A.size();
int Q = X.size();
vector<int> res(Q);
vector<ll> skalowanie;
for(auto i : A)
skalowanie.push_back(i);
for(auto i : V)
skalowanie.push_back(i);
sort(skalowanie.begin(), skalowanie.end());
map<ll, ll> skalowanie2;
for(ll i = 0; i < skalowanie.size(); ++i){
if(skalowanie2[skalowanie[i]] == 0) skalowanie2[skalowanie[i]] = i+1;
}
ll id = skalowanie.size()+7;
p = 0, k = id;
val = -INF;
update(1, 1, id);
for(ll i = 0; i < n; ++i){
A[i] = skalowanie2[A[i]]++;
p = 0, k = (lower_bound(skalowanie.begin(), skalowanie.end(), skalowanie[A[i]-1]) - skalowanie.begin());
val = 1;
update(1, 1, id);
p = k = A[i];
val = INF + i;
update(1, 1, id);
}
for(ll i = 0; i < Q; ++i){
p = 0, k = (lower_bound(skalowanie.begin(), skalowanie.end(), skalowanie[A[X[i]]-1]) - skalowanie.begin());
val = -1;
update(1, 1, id);
p = k = A[X[i]];
val = -INF;
update(1, 1, id);
A[X[i]] = skalowanie2[V[i]]++;
p = 0, k = (lower_bound(skalowanie.begin(), skalowanie.end(), skalowanie[A[X[i]]-1]) - skalowanie.begin());
val = 1;
update(1, 1, id);
p = k = A[X[i]];
val = INF + X[i];
update(1, 1, id);
p = 0, k = id;
res[i] = query(1, 1, id) - n + 1;
}
return res;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:76:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(ll i = 0; i < skalowanie.size(); ++i){
| ~~^~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2384 KB |
Output is correct |
2 |
Correct |
2 ms |
2640 KB |
Output is correct |
3 |
Correct |
5 ms |
2896 KB |
Output is correct |
4 |
Correct |
5 ms |
2760 KB |
Output is correct |
5 |
Correct |
5 ms |
2896 KB |
Output is correct |
6 |
Correct |
5 ms |
2896 KB |
Output is correct |
7 |
Correct |
4 ms |
2768 KB |
Output is correct |
8 |
Correct |
6 ms |
2896 KB |
Output is correct |
9 |
Correct |
5 ms |
2896 KB |
Output is correct |
10 |
Correct |
4 ms |
2872 KB |
Output is correct |
11 |
Correct |
4 ms |
2640 KB |
Output is correct |
12 |
Correct |
4 ms |
2640 KB |
Output is correct |
13 |
Correct |
4 ms |
2640 KB |
Output is correct |
14 |
Correct |
4 ms |
2640 KB |
Output is correct |
15 |
Correct |
5 ms |
2892 KB |
Output is correct |
16 |
Correct |
5 ms |
2640 KB |
Output is correct |
17 |
Correct |
4 ms |
2848 KB |
Output is correct |
18 |
Correct |
5 ms |
2640 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2384 KB |
Output is correct |
2 |
Correct |
2 ms |
2640 KB |
Output is correct |
3 |
Correct |
5 ms |
2896 KB |
Output is correct |
4 |
Correct |
5 ms |
2760 KB |
Output is correct |
5 |
Correct |
5 ms |
2896 KB |
Output is correct |
6 |
Correct |
5 ms |
2896 KB |
Output is correct |
7 |
Correct |
4 ms |
2768 KB |
Output is correct |
8 |
Correct |
6 ms |
2896 KB |
Output is correct |
9 |
Correct |
5 ms |
2896 KB |
Output is correct |
10 |
Correct |
4 ms |
2872 KB |
Output is correct |
11 |
Correct |
4 ms |
2640 KB |
Output is correct |
12 |
Correct |
4 ms |
2640 KB |
Output is correct |
13 |
Correct |
4 ms |
2640 KB |
Output is correct |
14 |
Correct |
4 ms |
2640 KB |
Output is correct |
15 |
Correct |
5 ms |
2892 KB |
Output is correct |
16 |
Correct |
5 ms |
2640 KB |
Output is correct |
17 |
Correct |
4 ms |
2848 KB |
Output is correct |
18 |
Correct |
5 ms |
2640 KB |
Output is correct |
19 |
Correct |
19 ms |
3920 KB |
Output is correct |
20 |
Correct |
22 ms |
4256 KB |
Output is correct |
21 |
Correct |
20 ms |
4304 KB |
Output is correct |
22 |
Correct |
22 ms |
4176 KB |
Output is correct |
23 |
Correct |
20 ms |
4088 KB |
Output is correct |
24 |
Correct |
18 ms |
4176 KB |
Output is correct |
25 |
Correct |
18 ms |
3920 KB |
Output is correct |
26 |
Correct |
18 ms |
7760 KB |
Output is correct |
27 |
Correct |
19 ms |
5712 KB |
Output is correct |
28 |
Correct |
17 ms |
7780 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
7380 KB |
Output is correct |
2 |
Correct |
42 ms |
8392 KB |
Output is correct |
3 |
Correct |
78 ms |
9276 KB |
Output is correct |
4 |
Correct |
79 ms |
9148 KB |
Output is correct |
5 |
Correct |
76 ms |
9144 KB |
Output is correct |
6 |
Correct |
74 ms |
9340 KB |
Output is correct |
7 |
Correct |
75 ms |
9404 KB |
Output is correct |
8 |
Correct |
74 ms |
9416 KB |
Output is correct |
9 |
Correct |
72 ms |
9416 KB |
Output is correct |
10 |
Correct |
68 ms |
9520 KB |
Output is correct |
11 |
Correct |
62 ms |
9404 KB |
Output is correct |
12 |
Correct |
63 ms |
9448 KB |
Output is correct |
13 |
Correct |
62 ms |
9284 KB |
Output is correct |
14 |
Correct |
63 ms |
9404 KB |
Output is correct |
15 |
Correct |
77 ms |
9404 KB |
Output is correct |
16 |
Correct |
62 ms |
9496 KB |
Output is correct |
17 |
Correct |
63 ms |
9408 KB |
Output is correct |
18 |
Correct |
59 ms |
9404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
2384 KB |
Output is correct |
2 |
Correct |
2 ms |
2640 KB |
Output is correct |
3 |
Correct |
5 ms |
2896 KB |
Output is correct |
4 |
Correct |
5 ms |
2760 KB |
Output is correct |
5 |
Correct |
5 ms |
2896 KB |
Output is correct |
6 |
Correct |
5 ms |
2896 KB |
Output is correct |
7 |
Correct |
4 ms |
2768 KB |
Output is correct |
8 |
Correct |
6 ms |
2896 KB |
Output is correct |
9 |
Correct |
5 ms |
2896 KB |
Output is correct |
10 |
Correct |
4 ms |
2872 KB |
Output is correct |
11 |
Correct |
4 ms |
2640 KB |
Output is correct |
12 |
Correct |
4 ms |
2640 KB |
Output is correct |
13 |
Correct |
4 ms |
2640 KB |
Output is correct |
14 |
Correct |
4 ms |
2640 KB |
Output is correct |
15 |
Correct |
5 ms |
2892 KB |
Output is correct |
16 |
Correct |
5 ms |
2640 KB |
Output is correct |
17 |
Correct |
4 ms |
2848 KB |
Output is correct |
18 |
Correct |
5 ms |
2640 KB |
Output is correct |
19 |
Correct |
19 ms |
3920 KB |
Output is correct |
20 |
Correct |
22 ms |
4256 KB |
Output is correct |
21 |
Correct |
20 ms |
4304 KB |
Output is correct |
22 |
Correct |
22 ms |
4176 KB |
Output is correct |
23 |
Correct |
20 ms |
4088 KB |
Output is correct |
24 |
Correct |
18 ms |
4176 KB |
Output is correct |
25 |
Correct |
18 ms |
3920 KB |
Output is correct |
26 |
Correct |
18 ms |
7760 KB |
Output is correct |
27 |
Correct |
19 ms |
5712 KB |
Output is correct |
28 |
Correct |
17 ms |
7780 KB |
Output is correct |
29 |
Correct |
14 ms |
7380 KB |
Output is correct |
30 |
Correct |
42 ms |
8392 KB |
Output is correct |
31 |
Correct |
78 ms |
9276 KB |
Output is correct |
32 |
Correct |
79 ms |
9148 KB |
Output is correct |
33 |
Correct |
76 ms |
9144 KB |
Output is correct |
34 |
Correct |
74 ms |
9340 KB |
Output is correct |
35 |
Correct |
75 ms |
9404 KB |
Output is correct |
36 |
Correct |
74 ms |
9416 KB |
Output is correct |
37 |
Correct |
72 ms |
9416 KB |
Output is correct |
38 |
Correct |
68 ms |
9520 KB |
Output is correct |
39 |
Correct |
62 ms |
9404 KB |
Output is correct |
40 |
Correct |
63 ms |
9448 KB |
Output is correct |
41 |
Correct |
62 ms |
9284 KB |
Output is correct |
42 |
Correct |
63 ms |
9404 KB |
Output is correct |
43 |
Correct |
77 ms |
9404 KB |
Output is correct |
44 |
Correct |
62 ms |
9496 KB |
Output is correct |
45 |
Correct |
63 ms |
9408 KB |
Output is correct |
46 |
Correct |
59 ms |
9404 KB |
Output is correct |
47 |
Correct |
701 ms |
48960 KB |
Output is correct |
48 |
Correct |
3082 ms |
123096 KB |
Output is correct |
49 |
Correct |
3518 ms |
130532 KB |
Output is correct |
50 |
Correct |
3070 ms |
130500 KB |
Output is correct |
51 |
Correct |
3403 ms |
130600 KB |
Output is correct |
52 |
Correct |
3355 ms |
130560 KB |
Output is correct |
53 |
Correct |
3172 ms |
130472 KB |
Output is correct |
54 |
Correct |
3010 ms |
130728 KB |
Output is correct |
55 |
Correct |
3051 ms |
130728 KB |
Output is correct |
56 |
Correct |
2605 ms |
130696 KB |
Output is correct |
57 |
Correct |
3216 ms |
130524 KB |
Output is correct |
58 |
Correct |
2865 ms |
130560 KB |
Output is correct |
59 |
Correct |
2457 ms |
121512 KB |
Output is correct |
60 |
Correct |
2605 ms |
121584 KB |
Output is correct |
61 |
Correct |
2666 ms |
121512 KB |
Output is correct |
62 |
Correct |
2615 ms |
117412 KB |
Output is correct |
63 |
Correct |
2424 ms |
117432 KB |
Output is correct |
64 |
Correct |
2667 ms |
117424 KB |
Output is correct |
65 |
Correct |
2449 ms |
113004 KB |
Output is correct |
66 |
Correct |
2521 ms |
113056 KB |
Output is correct |
67 |
Correct |
2577 ms |
113008 KB |
Output is correct |