//#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int> > lis;
long long int seg[1<<21];
long long int lazy[1<<21];
void upd(int b){
seg[b]+=lazy[b];
if(b*2+2<(1<<21)){
lazy[b*2+1]+=lazy[b];
lazy[b*2+2]+=lazy[b];
}
lazy[b]=0;
}
inline void add(int b,int l,int r,int ll,int rr,long long int x){
upd(b);
if(r<=ll||rr<=l){
return;
}
if(ll<=l&&r<=rr){
lazy[b]+=x;
upd(b);
return;
}
add(b*2+1,l,(l+r)>>1,ll,rr,x);
add(b*2+2,(l+r)>>1,r,ll,rr,x);
seg[b]=max(seg[b*2+1],seg[b*2+2]);
}
int get_id(int pos,int val){
return lower_bound(lis.begin(),lis.end(),make_pair(val,pos))-lis.begin();
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
for(int i=0;i<A.size();i++){
lis.push_back(make_pair(A[i],i));
}
for(int i=0;i<X.size();i++){
lis.push_back(make_pair(V[i],X[i]));
}
sort(lis.begin(),lis.end());
lis.erase(unique(lis.begin(),lis.end()),lis.end());
for(int i=0;i<A.size();i++){
int z=get_id(i,A[i]);
add(0,0,lis.size(),z,z+1,i);
add(0,0,lis.size(),lower_bound(lis.begin(),lis.end(),make_pair(A[i],-1))-lis.begin(),lis.size(),-1);
}
vector<int> res;
for(int ii=0;ii<X.size();ii++){
int i=X[ii];
int z=get_id(i,A[i]);
add(0,0,lis.size(),z,z+1,-i);
add(0,0,lis.size(),lower_bound(lis.begin(),lis.end(),make_pair(A[i],-1))-lis.begin(),lis.size(),1);
A[i]=V[ii];
z=get_id(i,A[i]);
add(0,0,lis.size(),z,z+1,i);
add(0,0,lis.size(),lower_bound(lis.begin(),lis.end(),make_pair(A[i],-1))-lis.begin(),lis.size(),-1);
upd(0);
res.push_back(seg[0]+1);
}
return res;
}
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<A.size();i++){
~^~~~~~~~~
bubblesort2.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<X.size();i++){
~^~~~~~~~~
bubblesort2.cpp:45:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<A.size();i++){
~^~~~~~~~~
bubblesort2.cpp:51:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int ii=0;ii<X.size();ii++){
~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
612 KB |
Output is correct |
| 3 |
Correct |
9 ms |
820 KB |
Output is correct |
| 4 |
Correct |
8 ms |
820 KB |
Output is correct |
| 5 |
Correct |
8 ms |
820 KB |
Output is correct |
| 6 |
Correct |
8 ms |
828 KB |
Output is correct |
| 7 |
Correct |
7 ms |
828 KB |
Output is correct |
| 8 |
Correct |
9 ms |
892 KB |
Output is correct |
| 9 |
Correct |
12 ms |
892 KB |
Output is correct |
| 10 |
Correct |
9 ms |
892 KB |
Output is correct |
| 11 |
Correct |
8 ms |
892 KB |
Output is correct |
| 12 |
Correct |
9 ms |
892 KB |
Output is correct |
| 13 |
Correct |
13 ms |
916 KB |
Output is correct |
| 14 |
Correct |
10 ms |
952 KB |
Output is correct |
| 15 |
Correct |
11 ms |
952 KB |
Output is correct |
| 16 |
Correct |
8 ms |
952 KB |
Output is correct |
| 17 |
Correct |
11 ms |
952 KB |
Output is correct |
| 18 |
Correct |
8 ms |
952 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
612 KB |
Output is correct |
| 3 |
Correct |
9 ms |
820 KB |
Output is correct |
| 4 |
Correct |
8 ms |
820 KB |
Output is correct |
| 5 |
Correct |
8 ms |
820 KB |
Output is correct |
| 6 |
Correct |
8 ms |
828 KB |
Output is correct |
| 7 |
Correct |
7 ms |
828 KB |
Output is correct |
| 8 |
Correct |
9 ms |
892 KB |
Output is correct |
| 9 |
Correct |
12 ms |
892 KB |
Output is correct |
| 10 |
Correct |
9 ms |
892 KB |
Output is correct |
| 11 |
Correct |
8 ms |
892 KB |
Output is correct |
| 12 |
Correct |
9 ms |
892 KB |
Output is correct |
| 13 |
Correct |
13 ms |
916 KB |
Output is correct |
| 14 |
Correct |
10 ms |
952 KB |
Output is correct |
| 15 |
Correct |
11 ms |
952 KB |
Output is correct |
| 16 |
Correct |
8 ms |
952 KB |
Output is correct |
| 17 |
Correct |
11 ms |
952 KB |
Output is correct |
| 18 |
Correct |
8 ms |
952 KB |
Output is correct |
| 19 |
Correct |
33 ms |
1836 KB |
Output is correct |
| 20 |
Correct |
45 ms |
1964 KB |
Output is correct |
| 21 |
Correct |
39 ms |
1964 KB |
Output is correct |
| 22 |
Correct |
33 ms |
1964 KB |
Output is correct |
| 23 |
Correct |
39 ms |
1964 KB |
Output is correct |
| 24 |
Correct |
32 ms |
1964 KB |
Output is correct |
| 25 |
Correct |
32 ms |
1964 KB |
Output is correct |
| 26 |
Correct |
45 ms |
1964 KB |
Output is correct |
| 27 |
Correct |
29 ms |
1964 KB |
Output is correct |
| 28 |
Correct |
26 ms |
1964 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
2856 KB |
Output is correct |
| 2 |
Correct |
165 ms |
5148 KB |
Output is correct |
| 3 |
Correct |
277 ms |
9248 KB |
Output is correct |
| 4 |
Correct |
275 ms |
9276 KB |
Output is correct |
| 5 |
Correct |
277 ms |
9428 KB |
Output is correct |
| 6 |
Correct |
235 ms |
9428 KB |
Output is correct |
| 7 |
Correct |
246 ms |
9428 KB |
Output is correct |
| 8 |
Correct |
265 ms |
9428 KB |
Output is correct |
| 9 |
Correct |
200 ms |
9428 KB |
Output is correct |
| 10 |
Correct |
152 ms |
9428 KB |
Output is correct |
| 11 |
Correct |
182 ms |
9428 KB |
Output is correct |
| 12 |
Correct |
181 ms |
9428 KB |
Output is correct |
| 13 |
Correct |
196 ms |
9428 KB |
Output is correct |
| 14 |
Correct |
249 ms |
9428 KB |
Output is correct |
| 15 |
Correct |
187 ms |
9428 KB |
Output is correct |
| 16 |
Correct |
168 ms |
9428 KB |
Output is correct |
| 17 |
Correct |
233 ms |
9428 KB |
Output is correct |
| 18 |
Correct |
165 ms |
9428 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
376 KB |
Output is correct |
| 2 |
Correct |
5 ms |
612 KB |
Output is correct |
| 3 |
Correct |
9 ms |
820 KB |
Output is correct |
| 4 |
Correct |
8 ms |
820 KB |
Output is correct |
| 5 |
Correct |
8 ms |
820 KB |
Output is correct |
| 6 |
Correct |
8 ms |
828 KB |
Output is correct |
| 7 |
Correct |
7 ms |
828 KB |
Output is correct |
| 8 |
Correct |
9 ms |
892 KB |
Output is correct |
| 9 |
Correct |
12 ms |
892 KB |
Output is correct |
| 10 |
Correct |
9 ms |
892 KB |
Output is correct |
| 11 |
Correct |
8 ms |
892 KB |
Output is correct |
| 12 |
Correct |
9 ms |
892 KB |
Output is correct |
| 13 |
Correct |
13 ms |
916 KB |
Output is correct |
| 14 |
Correct |
10 ms |
952 KB |
Output is correct |
| 15 |
Correct |
11 ms |
952 KB |
Output is correct |
| 16 |
Correct |
8 ms |
952 KB |
Output is correct |
| 17 |
Correct |
11 ms |
952 KB |
Output is correct |
| 18 |
Correct |
8 ms |
952 KB |
Output is correct |
| 19 |
Correct |
33 ms |
1836 KB |
Output is correct |
| 20 |
Correct |
45 ms |
1964 KB |
Output is correct |
| 21 |
Correct |
39 ms |
1964 KB |
Output is correct |
| 22 |
Correct |
33 ms |
1964 KB |
Output is correct |
| 23 |
Correct |
39 ms |
1964 KB |
Output is correct |
| 24 |
Correct |
32 ms |
1964 KB |
Output is correct |
| 25 |
Correct |
32 ms |
1964 KB |
Output is correct |
| 26 |
Correct |
45 ms |
1964 KB |
Output is correct |
| 27 |
Correct |
29 ms |
1964 KB |
Output is correct |
| 28 |
Correct |
26 ms |
1964 KB |
Output is correct |
| 29 |
Correct |
39 ms |
2856 KB |
Output is correct |
| 30 |
Correct |
165 ms |
5148 KB |
Output is correct |
| 31 |
Correct |
277 ms |
9248 KB |
Output is correct |
| 32 |
Correct |
275 ms |
9276 KB |
Output is correct |
| 33 |
Correct |
277 ms |
9428 KB |
Output is correct |
| 34 |
Correct |
235 ms |
9428 KB |
Output is correct |
| 35 |
Correct |
246 ms |
9428 KB |
Output is correct |
| 36 |
Correct |
265 ms |
9428 KB |
Output is correct |
| 37 |
Correct |
200 ms |
9428 KB |
Output is correct |
| 38 |
Correct |
152 ms |
9428 KB |
Output is correct |
| 39 |
Correct |
182 ms |
9428 KB |
Output is correct |
| 40 |
Correct |
181 ms |
9428 KB |
Output is correct |
| 41 |
Correct |
196 ms |
9428 KB |
Output is correct |
| 42 |
Correct |
249 ms |
9428 KB |
Output is correct |
| 43 |
Correct |
187 ms |
9428 KB |
Output is correct |
| 44 |
Correct |
168 ms |
9428 KB |
Output is correct |
| 45 |
Correct |
233 ms |
9428 KB |
Output is correct |
| 46 |
Correct |
165 ms |
9428 KB |
Output is correct |
| 47 |
Correct |
1113 ms |
32708 KB |
Output is correct |
| 48 |
Correct |
3345 ms |
55560 KB |
Output is correct |
| 49 |
Correct |
3625 ms |
57176 KB |
Output is correct |
| 50 |
Correct |
4050 ms |
57248 KB |
Output is correct |
| 51 |
Correct |
3822 ms |
57248 KB |
Output is correct |
| 52 |
Correct |
4088 ms |
57248 KB |
Output is correct |
| 53 |
Correct |
4601 ms |
57248 KB |
Output is correct |
| 54 |
Correct |
3954 ms |
57248 KB |
Output is correct |
| 55 |
Correct |
4113 ms |
57248 KB |
Output is correct |
| 56 |
Correct |
3410 ms |
57248 KB |
Output is correct |
| 57 |
Correct |
3594 ms |
57248 KB |
Output is correct |
| 58 |
Correct |
3242 ms |
57352 KB |
Output is correct |
| 59 |
Correct |
3085 ms |
57352 KB |
Output is correct |
| 60 |
Correct |
2965 ms |
57352 KB |
Output is correct |
| 61 |
Correct |
2855 ms |
57352 KB |
Output is correct |
| 62 |
Correct |
3112 ms |
57352 KB |
Output is correct |
| 63 |
Correct |
3435 ms |
57352 KB |
Output is correct |
| 64 |
Correct |
3163 ms |
57352 KB |
Output is correct |
| 65 |
Correct |
2915 ms |
57352 KB |
Output is correct |
| 66 |
Correct |
2846 ms |
57352 KB |
Output is correct |
| 67 |
Correct |
2867 ms |
57352 KB |
Output is correct |
