#include<bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;
const int N=500500;
int a[N];
int n;
set<pair<int,int>>all;
int sz1=100;
int sz2=0;
int memos[N];
void reb_int(){
}
struct fen1{
vector<int>ys;
vector<int>t;
int n;
void init(){
t.resize(ys.size());
n=t.size();
}
int get(int r){
--r;
r=lower_bound(ys.begin(),ys.end(),r)-ys.begin();
int ans=0;
for(;r>=0;r&=r+1,r--)
ans+=t[r];
return ans;
}
void ch(int x,int y){
x=lower_bound(ys.begin(),ys.end(),x)-ys.begin();
for(;x<n;x|=x+1)
t[x]+=y;
}
int get(int l,int r){
return get(r)-get(l);
}
} fens[N];
void ch(int x,int y,int val){
for(;x<N;x|=x+1)
fens[x].ch(y,val);
}
void recalc(int i){
int ans=i;
int r=i-1;
for(;r>=0;r&=r+1,--r)
ans-=fens[r].get(0,a[i]+1);
memos[i]=ans;
}
vector<pair<int,int>>pts;
void init_fens(){
int ptr=0;
for(int i=0;i<n;++i){
while(ptr<pts.size()&&pts[ptr].first<i)++ptr;
for(int k=i;k<n;k|=k+1)
for(int j=ptr;j<pts.size()&&pts[j].first==i;++j)
fens[k].ys.push_back(pts[j].second);
}
for(int i=0;i<n;++i)fens[i].init();
}
int cnt=0;
void upd(int i,int coef){
auto p=make_pair(a[i],i);
ch(i,a[i],coef);
if(coef==-1)
all.erase(p);
if(coef==1)
all.insert(p);
vector<int>kek;
auto it=all.begin();
for(int i=0;i<sz2;++i,++it){
kek.push_back(it->second);
}
for(int i=0;i<sz1;++i)kek.push_back(n-i-1);
sort(kek.begin(),kek.end());
kek.erase(unique(kek.begin(),kek.end()),kek.end());
for(int x:kek){
if(i<x&&a[i]>a[x])memos[x]+=coef;
}
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> x,std::vector<int> v){
n=A.size();
sz1=min(sz1,n);
sz2=min(sz2,n);
int q=x.size();
copy(A.begin(),A.end(),a);
for(int i=0;i<n;++i){
pts.emplace_back(i,a[i]);
}
for(int i=0;i<q;++i)pts.emplace_back(x[i],v[i]);
sort(pts.begin(),pts.end());
init_fens();
for(int i=0;i<n;++i)upd(i,1);
vector<int>answer(q);
for(int i=0;i<q;++i){
upd(x[i],-1);
a[x[i]]=v[i];
upd(x[i],1);
recalc(x[i]);
for(int j=0;j<sz1;++j){
recalc(n-j-1);
answer[i]=max(answer[i],memos[n-j-1]);
}
}
return answer;
}
Compilation message
bubblesort2.cpp: In function 'void init_fens()':
bubblesort2.cpp:60:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ptr<pts.size()&&pts[ptr].first<i)++ptr;
~~~^~~~~~~~~~~
bubblesort2.cpp:62:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=ptr;j<pts.size()&&pts[j].first==i;++j)
~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
27904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
27904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
187 ms |
33240 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
42 ms |
27904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
