#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9+1;
const int sz=8192;
int tree[sz*2];
vector<int> pr;
int sum(int i) {
int ret=0;
while (i>0) {
ret+=tree[i];
i-=(i&-i);
}
return ret;
}
void update(int i,int x) {
while (i<sz) {
tree[i]+=x;
i+=(i&-i);
}
}
int cal(vector<int> v) {
int ret=0;
memset(tree,0,sizeof(tree));
for(int i=0;i<v.size();i++) {
ret=max(ret,sum(sz-1)-sum(v[i]));
update(v[i],1);
}
return ret;
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
int q=X.size();
vector<int> ret(q);
pr.push_back(-1);
for(int i=0;i<A.size();i++) {
pr.push_back(A[i]);
}
for(int i=0;i<q;i++) {
pr.push_back(V[i]);
}
sort(pr.begin(),pr.end());
pr.erase(unique(pr.begin(),pr.end()),pr.end());
for(int i=0;i<A.size();i++) {
A[i]=lower_bound(pr.begin(),pr.end(),A[i])-pr.begin();
}
for(int i=0;i<q;i++) {
V[i]=lower_bound(pr.begin(),pr.end(),V[i])-pr.begin();
}
for (int j=0;j<q;j++) {
A[X[j]]=V[j];
ret[j]=cal(A);
}
return ret;
}
Compilation message
bubblesort2.cpp: In function 'int cal(std::vector<int>)':
bubblesort2.cpp:29:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i=0;i<v.size();i++) {
| ~^~~~~~~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:40:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int i=0;i<A.size();i++) {
| ~^~~~~~~~~
bubblesort2.cpp:48:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i=0;i<A.size();i++) {
| ~^~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
388 KB |
Output is correct |
2 |
Correct |
33 ms |
372 KB |
Output is correct |
3 |
Correct |
207 ms |
420 KB |
Output is correct |
4 |
Correct |
171 ms |
420 KB |
Output is correct |
5 |
Correct |
165 ms |
424 KB |
Output is correct |
6 |
Correct |
158 ms |
428 KB |
Output is correct |
7 |
Correct |
199 ms |
420 KB |
Output is correct |
8 |
Correct |
166 ms |
420 KB |
Output is correct |
9 |
Correct |
166 ms |
332 KB |
Output is correct |
10 |
Correct |
160 ms |
432 KB |
Output is correct |
11 |
Correct |
164 ms |
420 KB |
Output is correct |
12 |
Correct |
176 ms |
424 KB |
Output is correct |
13 |
Correct |
161 ms |
332 KB |
Output is correct |
14 |
Correct |
159 ms |
428 KB |
Output is correct |
15 |
Correct |
166 ms |
420 KB |
Output is correct |
16 |
Correct |
171 ms |
424 KB |
Output is correct |
17 |
Correct |
179 ms |
428 KB |
Output is correct |
18 |
Correct |
194 ms |
428 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
388 KB |
Output is correct |
2 |
Correct |
33 ms |
372 KB |
Output is correct |
3 |
Correct |
207 ms |
420 KB |
Output is correct |
4 |
Correct |
171 ms |
420 KB |
Output is correct |
5 |
Correct |
165 ms |
424 KB |
Output is correct |
6 |
Correct |
158 ms |
428 KB |
Output is correct |
7 |
Correct |
199 ms |
420 KB |
Output is correct |
8 |
Correct |
166 ms |
420 KB |
Output is correct |
9 |
Correct |
166 ms |
332 KB |
Output is correct |
10 |
Correct |
160 ms |
432 KB |
Output is correct |
11 |
Correct |
164 ms |
420 KB |
Output is correct |
12 |
Correct |
176 ms |
424 KB |
Output is correct |
13 |
Correct |
161 ms |
332 KB |
Output is correct |
14 |
Correct |
159 ms |
428 KB |
Output is correct |
15 |
Correct |
166 ms |
420 KB |
Output is correct |
16 |
Correct |
171 ms |
424 KB |
Output is correct |
17 |
Correct |
179 ms |
428 KB |
Output is correct |
18 |
Correct |
194 ms |
428 KB |
Output is correct |
19 |
Incorrect |
2027 ms |
660 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2462 ms |
844 KB |
Output is correct |
2 |
Execution timed out |
9060 ms |
1608 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
14 ms |
388 KB |
Output is correct |
2 |
Correct |
33 ms |
372 KB |
Output is correct |
3 |
Correct |
207 ms |
420 KB |
Output is correct |
4 |
Correct |
171 ms |
420 KB |
Output is correct |
5 |
Correct |
165 ms |
424 KB |
Output is correct |
6 |
Correct |
158 ms |
428 KB |
Output is correct |
7 |
Correct |
199 ms |
420 KB |
Output is correct |
8 |
Correct |
166 ms |
420 KB |
Output is correct |
9 |
Correct |
166 ms |
332 KB |
Output is correct |
10 |
Correct |
160 ms |
432 KB |
Output is correct |
11 |
Correct |
164 ms |
420 KB |
Output is correct |
12 |
Correct |
176 ms |
424 KB |
Output is correct |
13 |
Correct |
161 ms |
332 KB |
Output is correct |
14 |
Correct |
159 ms |
428 KB |
Output is correct |
15 |
Correct |
166 ms |
420 KB |
Output is correct |
16 |
Correct |
171 ms |
424 KB |
Output is correct |
17 |
Correct |
179 ms |
428 KB |
Output is correct |
18 |
Correct |
194 ms |
428 KB |
Output is correct |
19 |
Incorrect |
2027 ms |
660 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |