#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
int seg[2][2000001];
int arr[500001];
void build(int p,int l,int r){
if(l==r){
seg[0][p] = arr[l];
seg[1][p] = arr[l];
return ;
}
int md = (l+r)/2;
build(p*2,l,md);
build(p*2+1,md+1,r);
seg[0][p] = min(seg[0][p*2],seg[0][p*2+1]);
seg[1][p] = max(seg[1][p*2],seg[1][p*2+1]);
}
void update(int p,int l,int r,int ind){
if(l==r){
seg[0][p] = arr[l];
seg[1][p] = arr[l];
return ;
}
int md = (l+r)/2;
if(ind<=md)update(p*2,l,md,ind);
else update(p*2+1,md+1,r,ind);
seg[0][p] = min(seg[0][p*2],seg[0][p*2+1]);
seg[1][p] = max(seg[1][p*2],seg[1][p*2+1]);
}
long long qu(int p,int l,int r,int lq,int rq,int ty){
if(l>=lq&&r<=rq)return seg[ty][p];
if(r<lq||l>rq)return (ty==0?1e18:-1e18);
int md = (l+r)/2;
if(ty==0)return min(qu(p*2,l,md,lq,rq,ty),qu(p*2+1,md+1,r,lq,rq,ty));
if(ty==1)return max(qu(p*2,l,md,lq,rq,ty),qu(p*2+1,md+1,r,lq,rq,ty));
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
for(int i= 0;i<A.size();i++)arr[i+1] = A[i];
build(1,1,A.size());
vector<int> d;
for(int i = 0;i<X.size();i++){
arr[X[i]+1]= V[i];
update(1,1,A.size(),X[i]+1);
long long ans = 0;
int l = 1 , r = X[i];
while(l<=r){
long long mid = (l+r)/2;
if(qu(1,1,A.size(),1,mid,1)>V[i]){
ans=max(ans,(X[i]+1)-mid);
r = mid-1;
}else l = mid+1;
}
l = X[i]+2,r = A.size();
while(l<=r){
long long mid = (l+r)/2;
if(qu(1,1,A.size(),mid,A.size(),0)<V[i]){
ans=max(ans,mid-(X[i]+1));
l=mid+1;
}else r = mid-1;
}
d.push_back(ans);
}
return d;
}
/*int main(){
vector<int> v= countScans({1,2,3,4},{0,2},{3,1});
for(auto i:v)cout<<i<<"\n";
}*/
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i= 0;i<A.size();i++)arr[i+1] = A[i];
| ~^~~~~~~~~
bubblesort2.cpp:42:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for(int i = 0;i<X.size();i++){
| ~^~~~~~~~~
bubblesort2.cpp: In function 'long long int qu(int, int, int, int, int, int)':
bubblesort2.cpp:37:1: warning: control reaches end of non-void function [-Wreturn-type]
37 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
1296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
