#include "bubblesort2.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using D=long double;
using P=pair<ll,ll>;
struct BIT{
vector<int> bit;
BIT(int n){
bit.resize(++n);
}
void add(int k,int x){
for(++k;k<bit.size();k+=k&-k){
bit[k]+=x;
}
}
int get(int k){
int res=0;
for(++k;k>0;k-=k&-k){
res+=bit[k];
}
return res;
}
};
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
int n=A.size(),q=X.size();
assert(n<=8000&&q<=8000);
vector<int> v;
for(int i=0;i<n;i++){
v.eb(A[i]);
}
for(int i=0;i<q;i++){
v.eb(V[i]);
}
sort(all(v));
v.erase(unique(all(v)),v.end());
int m=v.size();
for(int i=0;i<n;i++){
A[i]=lower_bound(all(v),A[i])-v.begin();
}
vector<int> res(q);
for(int i=0;i<q;i++){
V[i]=lower_bound(all(v),V[i])-v.begin();
A[X[i]]=V[i];
BIT bit(m+5);
for(int j=0;j<n;j++){
res[i]=max(res[i],bit.get(m+1)-bit.get(A[j]));
bit.add(A[j],1);
}
}
return res;
}
Compilation message
bubblesort2.cpp: In member function 'void BIT::add(int, int)':
bubblesort2.cpp:15:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(++k;k<bit.size();k+=k&-k){
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
376 KB |
Output is correct |
| 2 |
Correct |
26 ms |
376 KB |
Output is correct |
| 3 |
Correct |
130 ms |
376 KB |
Output is correct |
| 4 |
Correct |
132 ms |
376 KB |
Output is correct |
| 5 |
Correct |
134 ms |
376 KB |
Output is correct |
| 6 |
Correct |
124 ms |
376 KB |
Output is correct |
| 7 |
Correct |
134 ms |
376 KB |
Output is correct |
| 8 |
Correct |
131 ms |
376 KB |
Output is correct |
| 9 |
Correct |
133 ms |
376 KB |
Output is correct |
| 10 |
Correct |
122 ms |
376 KB |
Output is correct |
| 11 |
Correct |
123 ms |
376 KB |
Output is correct |
| 12 |
Correct |
128 ms |
504 KB |
Output is correct |
| 13 |
Correct |
119 ms |
376 KB |
Output is correct |
| 14 |
Correct |
121 ms |
376 KB |
Output is correct |
| 15 |
Correct |
128 ms |
376 KB |
Output is correct |
| 16 |
Correct |
123 ms |
376 KB |
Output is correct |
| 17 |
Correct |
122 ms |
376 KB |
Output is correct |
| 18 |
Correct |
126 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
376 KB |
Output is correct |
| 2 |
Correct |
26 ms |
376 KB |
Output is correct |
| 3 |
Correct |
130 ms |
376 KB |
Output is correct |
| 4 |
Correct |
132 ms |
376 KB |
Output is correct |
| 5 |
Correct |
134 ms |
376 KB |
Output is correct |
| 6 |
Correct |
124 ms |
376 KB |
Output is correct |
| 7 |
Correct |
134 ms |
376 KB |
Output is correct |
| 8 |
Correct |
131 ms |
376 KB |
Output is correct |
| 9 |
Correct |
133 ms |
376 KB |
Output is correct |
| 10 |
Correct |
122 ms |
376 KB |
Output is correct |
| 11 |
Correct |
123 ms |
376 KB |
Output is correct |
| 12 |
Correct |
128 ms |
504 KB |
Output is correct |
| 13 |
Correct |
119 ms |
376 KB |
Output is correct |
| 14 |
Correct |
121 ms |
376 KB |
Output is correct |
| 15 |
Correct |
128 ms |
376 KB |
Output is correct |
| 16 |
Correct |
123 ms |
376 KB |
Output is correct |
| 17 |
Correct |
122 ms |
376 KB |
Output is correct |
| 18 |
Correct |
126 ms |
376 KB |
Output is correct |
| 19 |
Correct |
1852 ms |
676 KB |
Output is correct |
| 20 |
Correct |
2250 ms |
960 KB |
Output is correct |
| 21 |
Correct |
2233 ms |
888 KB |
Output is correct |
| 22 |
Correct |
2284 ms |
888 KB |
Output is correct |
| 23 |
Correct |
2115 ms |
888 KB |
Output is correct |
| 24 |
Correct |
2173 ms |
888 KB |
Output is correct |
| 25 |
Correct |
2009 ms |
888 KB |
Output is correct |
| 26 |
Correct |
1949 ms |
868 KB |
Output is correct |
| 27 |
Correct |
2070 ms |
876 KB |
Output is correct |
| 28 |
Correct |
2029 ms |
888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
1016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
376 KB |
Output is correct |
| 2 |
Correct |
26 ms |
376 KB |
Output is correct |
| 3 |
Correct |
130 ms |
376 KB |
Output is correct |
| 4 |
Correct |
132 ms |
376 KB |
Output is correct |
| 5 |
Correct |
134 ms |
376 KB |
Output is correct |
| 6 |
Correct |
124 ms |
376 KB |
Output is correct |
| 7 |
Correct |
134 ms |
376 KB |
Output is correct |
| 8 |
Correct |
131 ms |
376 KB |
Output is correct |
| 9 |
Correct |
133 ms |
376 KB |
Output is correct |
| 10 |
Correct |
122 ms |
376 KB |
Output is correct |
| 11 |
Correct |
123 ms |
376 KB |
Output is correct |
| 12 |
Correct |
128 ms |
504 KB |
Output is correct |
| 13 |
Correct |
119 ms |
376 KB |
Output is correct |
| 14 |
Correct |
121 ms |
376 KB |
Output is correct |
| 15 |
Correct |
128 ms |
376 KB |
Output is correct |
| 16 |
Correct |
123 ms |
376 KB |
Output is correct |
| 17 |
Correct |
122 ms |
376 KB |
Output is correct |
| 18 |
Correct |
126 ms |
376 KB |
Output is correct |
| 19 |
Correct |
1852 ms |
676 KB |
Output is correct |
| 20 |
Correct |
2250 ms |
960 KB |
Output is correct |
| 21 |
Correct |
2233 ms |
888 KB |
Output is correct |
| 22 |
Correct |
2284 ms |
888 KB |
Output is correct |
| 23 |
Correct |
2115 ms |
888 KB |
Output is correct |
| 24 |
Correct |
2173 ms |
888 KB |
Output is correct |
| 25 |
Correct |
2009 ms |
888 KB |
Output is correct |
| 26 |
Correct |
1949 ms |
868 KB |
Output is correct |
| 27 |
Correct |
2070 ms |
876 KB |
Output is correct |
| 28 |
Correct |
2029 ms |
888 KB |
Output is correct |
| 29 |
Runtime error |
10 ms |
1016 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 30 |
Halted |
0 ms |
0 KB |
- |
