#include <iostream>
#include <vector>
#include <map>
#include "bubblesort2.h"
using namespace std;
int find_min(int n,int l,int r,vector<int>& t,int x){
if(t[n]>=x)return -1;
if(l==r)return l;
int mid=(r+l)/2;
int ans=find_min((n<<1)+1,mid+1,r,t,x);
if(ans!=-1)return ans;
return find_min(n<<1,l,mid,t,x);
}
void p_upd(int n,int l,int r,vector<int>& t,int a,int x){
// cout<<l<<' '<<r<<' '<<x<<'\n';
if(l>a||r<a)return;
if(l==r&&l==a)t[n]=x;
else{
int mid=(r+l)/2;
p_upd(n<<1,l,mid,t,a,x);
p_upd((n<<1)+1,mid+1,r,t,a,x);
t[n]=max(t[n<<1],t[(n<<1)+1]);
}
}
void build(int n,int l,int r,vector<int>& t,vector<int>& li){
if(l==r)t[n]=li[l];
else{
int mid=(r+l)/2;
build(n<<1,l,mid,t,li);
build((n<<1)+1,mid+1,r,t,li);
t[n]=min(t[n<<1],t[(n<<1)+1]);
}
}
void p_updminimum(int n,int l,int r,vector<int>& t,int a,int x){
//cout<<l<<' '<<r<<' '<<a<<'\n';
if(l>a||r<a)return;
if(l==r&&l==a)t[n]=x;
else{
int mid=(r+l)/2;
p_updminimum(n<<1,l,mid,t,a,x);
p_updminimum((n<<1)+1,mid+1,r,t,a,x);
t[n]=min(t[n<<1],t[(n<<1)+1]);
}
}
int val(int n,int l,int r,vector<int>& t,int a,int b){
if(l>b||r<a)return -1;
if(l>=a&&r<=b)return t[n];
int mid=(r+l)/2;
int valls=val(n<<1,l,mid,t,a,b);
int valrs=val((n<<1)+1,mid+1,r,t,a,b);
return max(valls,valrs);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
int Q=X.size(),N=A.size();
vector<int> answer(Q),li;
map<int,int> nums;
for(auto x:A)nums[x]++;
for(auto x:V)nums[x]++;
for(auto x:nums)li.push_back(x.first);
int n=li.size();
vector<int> t_min(4*N),t_sol(4*N);
build(1,0,N-1,t_min,A);
for(int i=N-1;i>=0;i--){
int u=find_min(1,0,N-1,t_min,A[i]);
if(i<u){
int v=val(1,0,N-1,t_sol,i+1,u);
//cout<<v+1<<' ';
p_upd(1,0,N-1,t_sol,i,v+1);
}
}
for(int j=0;j<Q;j++) {
int u=find_min(1,0,N-1,t_min,V[j]);
A[X[j]]=V[j];
p_updminimum(1,0,N-1,t_min,X[j],V[j]);
if(X[j]<u){
int v=val(1,0,N-1,t_sol,X[j]+1,u);
p_upd(1,0,N-1,t_sol,X[j],v+1);
}
for(int i=X[j]-1;i>=0;i--){
int u=find_min(1,0,N-1,t_min,A[i]);
//cout<<A[i]<<' '<<i<<' '<<u<<'\n';
if(i<u){
int v=val(1,0,N-1,t_sol,i+1,u);
p_upd(1,0,N-1,t_sol,i,v+1);
}
}
answer[j]=t_sol[1];
}
//for(int x:answer)cout<<x<<' ';
return answer;
}
/*int main(){
vector<int> A={1,2,3,4},X={0,2},V={3,1};
countScans(A,X,V);
}*/
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:60:6: warning: unused variable 'n' [-Wunused-variable]
60 | int n=li.size();
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9030 ms |
1492 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
