#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "bubblesort2.h"
int ind[1000001];
int tree[4000001];
int lazy[4000001];
int tree2[1000001];
void u(int i,int j){
while(i<1000001){
tree2[i]+=j;
i+=(i&-i);
}
}
int s(int i){
int su=0;
while(i>0){
su+=tree2[i];
i-=(i&-i);
}
return su;
}
void push(int no,int l,int r){
tree[no]+=lazy[no];
if(l<r){
lazy[no*2+1]+=lazy[no];
lazy[no*2+2]+=lazy[no];
}
lazy[no]=0;
}
void update(int no,int l,int r,int aa,int bb,int val){
push(no,l,r);
if(r<aa or l>bb){
return;
}
if(aa<=l and r<=bb){
tree[no]+=val;
if(l<r){
lazy[no*2+1]+=val;
lazy[no*2+2]+=val;
}
}
else{
int mid=(l+r)/2;
update(no*2+1,l,mid,aa,bb,val);
update(no*2+2,mid+1,r,aa,bb,val);
tree[no]=max(tree[no*2+1],tree[no*2+2]);
}
}
void update2(int no,int l,int r,int i,int val){
push(no,l,r);
if(l==r){
tree[no]=val;
}
else{
int mid=(l+r)/2;
// push(no*2+1,l,mid);
// push(no*2+2,mid+1,r);
if(i<=mid){
update2(no*2+1,l,mid,i,val);
}
else{
update2(no*2+2,mid+1,r,i,val);
}
tree[no]=max(tree[no*2+1],tree[no*2+2]);
}
}
int val[500001];
std::vector<int> countScans(std::vector<int> it,std::vector<int> X,std::vector<int> V){
int q=X.size();
int n=it.size();
vector<pair<pair<int,int>,int>> cur;
for(int i=0;i<n;i++){
cur.pb({{it[i],i},i});
}
for(int i=0;i<q;i++){
cur.pb({{V[i],X[i]},i+n});
}
sort(cur.begin(),cur.end());
for(int i=0;i<n+q;i++){
ind[cur[i].b]=i;
}
for(int i=0;i<4*(n+q);i++){
tree[i]=-1e9;
}
vector<int> ans;
for(int i=0;i<n;i++){
u(ind[i]+1,1);
}
for(int i=0;i<n;i++){
val[i]=ind[i];
update2(0,0,n+q-1,ind[i],i-s(ind[i]));
}
for(int i=0;i<q;i++){
u(val[X[i]]+1,-1);
u(ind[i+n]+1,1);
update2(0,0,n+q-1,ind[i+n],X[i]-s(ind[i+n]));
update2(0,0,n+q-1,val[X[i]],-1e9);
if(ind[i+n]<n+q-1){
update(0,0,n+q-1,ind[i+n]+1,n+q-1,-1);
}
if(val[X[i]]<n+q-1){
update(0,0,n+q-1,val[X[i]]+1,n+q-1,1);
}
val[X[i]]=ind[i+n];
ans.pb(tree[0]);
}
/*for(auto j:ans){
cout<<j<<",";
}
cout<<endl;*/
return ans;
}
//#define endl '\n'
/*int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int nn,qq;
cin>>nn>>qq;
int pp;
vector<int> ac;
vector<int> bc;
vector<int> dc;
for(int i=0;i<nn;i++){
cin>>pp;
ac.pb(pp);
}
for(int i=0;i<qq;i++){
cin>>pp;
bc.pb(pp);
cin>>pp;
dc.pb(pp);
}
countScans(ac,bc,dc);
return 0;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
2332 KB |
Output is correct |
| 2 |
Incorrect |
58 ms |
4592 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
