#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&&t[n]<x)return l;
int mid=(r+l)/2;
if(t[(n<<1)+1]<x)return find_min((n<<1)+1,mid+1,r,t,x);
if(t[(n<<1)]<x)return find_min(n<<1,l,mid,t,x);
return -1;
}
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){
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 -1e9;
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);
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]);
//cout<<u<<' ';
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);
}
}
for(int j=0;j<Q;j++) {
A[X[j]]=V[j];
p_updminimum(1,0,N-1,t_min,X[j],V[j]);
for(int i=X[j];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];
//cout<<t_sol[1]<<' ';
}
//for(int ans:answer)cout<<ans<<' ';
return answer;
}
/*int main(){
vector<int> A={3,2,1,4},X={0,1,2,0},V={3,5,5,5};
countScans(A,X,V);
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9091 ms |
1464 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
