#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=300;
int sz2=300;
int memos[N];
void reb_int(){
}
struct fen1{
vector<int>ys;
vector<int>t;
int n;
void init(){
t.resize(ys.size());
sort(ys.begin(),ys.end());
ys.erase(unique(ys.begin(),ys.end()),ys.end());
n=t.size();
}
int get(int r){
r=lower_bound(ys.begin(),ys.end(),r)-ys.begin();
--r;
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;
// cerr<<fens[0].t[0]<<' '<<fens[1].t[0]<<' '<<fens[1].t[1]<<'\n';
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]);
}
auto it=all.begin();
for(int j=0;j<sz2;++j,++it){
recalc(it->second);
answer[i]=max(answer[i],memos[it->second]);
}
}
return answer;
}
Compilation message
bubblesort2.cpp: In function 'void init_fens()':
bubblesort2.cpp:64:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ptr<pts.size()&&pts[ptr].first<i)++ptr;
~~~^~~~~~~~~~~
bubblesort2.cpp:66: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 |
Correct |
145 ms |
28024 KB |
Output is correct |
| 2 |
Correct |
238 ms |
27896 KB |
Output is correct |
| 3 |
Correct |
522 ms |
28280 KB |
Output is correct |
| 4 |
Correct |
552 ms |
28276 KB |
Output is correct |
| 5 |
Incorrect |
510 ms |
28324 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
28024 KB |
Output is correct |
| 2 |
Correct |
238 ms |
27896 KB |
Output is correct |
| 3 |
Correct |
522 ms |
28280 KB |
Output is correct |
| 4 |
Correct |
552 ms |
28276 KB |
Output is correct |
| 5 |
Incorrect |
510 ms |
28324 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
490 ms |
33280 KB |
Output is correct |
| 2 |
Correct |
5726 ms |
37464 KB |
Output is correct |
| 3 |
Execution timed out |
9058 ms |
42348 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
28024 KB |
Output is correct |
| 2 |
Correct |
238 ms |
27896 KB |
Output is correct |
| 3 |
Correct |
522 ms |
28280 KB |
Output is correct |
| 4 |
Correct |
552 ms |
28276 KB |
Output is correct |
| 5 |
Incorrect |
510 ms |
28324 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
