#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 <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define ord tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update>
//#include "bubblesort2.h"
const int ss=700;
int ind2[500001];//current index of element i
vector<pair<int,int>> tt[500001/ss+1];
int ind[1000001];//index of each n+q-1 in seg tree
int lazy[4000001];
int tree4[4000001];
ord tree2[2000001];
int ac[500001];
void build(int no,int l,int r){
if(l==r){
tree2[no].insert({ac[l],ind[l]});
}
else{
int mid=(l+r)/2;
build(no*2+1,l,mid);
build(no*2+2,mid+1,r);
tree2[no]=tree2[no*2+1];
for(auto j:tree2[no*2+2]){
tree2[no].insert(j);
}
}
}
int query(int no,int l,int r,int aa,int bb,int val){
if(r<aa or l>bb){
return 0;
}
if(aa<=l and r<=bb){
return tree2[no].size()-tree2[no].order_of_key({val+1,0});
}
else{
int mid=(l+r)/2;
return query(no*2+1,l,mid,aa,bb,val)+query(no*2+2,mid+1,r,aa,bb,val);
}
}
void update3(int no,int l,int r,int ind5,pair<int,int> old,pair<int,int> nn){
if(r<ind5 or l>ind5){
return;
}
tree2[no].erase(old);
tree2[no].insert(nn);
if(l<r){
int mid=(l+r)/2;
update3(no*2+1,l,mid,ind5,old,nn);
update3(no*2+2,mid+1,r,ind5,old,nn);
}
}
void update(int no,int l,int r,int aa,int bb,int val){
if(lazy[no]>0 or lazy[no]<0){
tree4[no]+=lazy[no];
if(l<r){
lazy[no*2+1]+=lazy[no];
lazy[no*2+2]+=lazy[no];
}
lazy[no]=0;
}
if(r<aa or l>bb){
return;
}
if(aa<=l and r<=bb){
tree4[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);
tree4[no]=max(tree4[no*2+1],tree4[no*2+2]);
}
}
void update2(int no,int l,int r,int aa,int val){
if(lazy[no]>0 or lazy[no]<0){
tree4[no]+=lazy[no];
if(l<r){
lazy[no*2+1]+=lazy[no];
lazy[no*2+2]+=lazy[no];
}
lazy[no]=0;
}
/* if(r<aa or l>aa){
return;
}*/
if(l==r){
tree4[no]=val;
}
else{
int mid=(l+r)/2;
if(aa<=mid){
update2(no*2+1,l,mid,aa,val);
}
else{
update2(no*2+2,mid+1,r,aa,val);
}
tree4[no]=max(tree4[no*2+1],tree4[no*2+2]);
}
}
std::vector<int> countScans(std::vector<int> it,std::vector<int> X,std::vector<int> V){
int q=X.size();
int n=it.size();
for(int i=0;i<n;i++){
ac[i]=it[i];
}
//sqrt blocks process
for(int i=0;i<n;i++){
tt[i/ss].pb({it[i],i});
}
for(int i=0;i<q;i++){
tt[X[i]/ss].pb({V[i],i+n});
}
for(int i=0;i<=(n-1)/ss;i++){
sort(tt[i].begin(),tt[i].end());
}
//end
//process index
int co=-1;
for(int i=0;i<=(n-1)/ss;i++){
for(auto j:tt[i]){
co+=1;
ind[j.b]=co;
if(j.b<n){
ind2[j.b]=co;
}
}
}
build(0,0,n-1);
//end
for(int i=0;i<4*(n+q);i++){
tree4[i]=-1e9;
}
// memset(tree4,-1e9,sizeof(tree4));
//initial tree
ord kk;
for(int i=0;i<n;i++){
int cur=kk.size()-kk.order_of_key({it[i]+1,0});
update2(0,0,n+q-1,ind[i],cur);
kk.insert({it[i],i});
//cout<<i<<","<<cur<<endl;
}
//end
vector<int> ans;
/* for(int i=0;i<n+q;i++){
cout<<ind[i]<<":";
}
cout<<endl;*/
//pre-process with pbds
for(int ii=0;ii<q;ii++){
int ind3=X[ii];
int val=V[ii];
int l,r,cc;
update2(0,0,n+q-1,ind2[ind3],-1e9);
//remove pairs from mst
pair<int,int> old={it[ind3],ind2[ind3]};
pair<int,int> nn={val,ind[ii+n]};
update3(0,0,n-1,ind3,old,nn);
// update answer of current index
int x=0;
if(ind3>0){
/*for(int i=0;i<ind3;i++){
if(it[i]>val){
x+=1;
}
}*/
x=query(0,0,n-1,0,ind3-1,val);
}
// cout<<x<<endl;
update2(0,0,n+q-1,ind[ii+n],x);
//end
ind2[ind3]=ind[ii+n];
int kk=0;
if(val<it[ind3]){
l=val;
r=it[ind3]-1;
cc=-1;
}
else if(val>it[ind3]){
l=it[ind3];
r=val-1;
cc=1;
}
else{
ans.pb(tree4[0]);
continue;
}
// cout<<l<<","<<r<<","<<cc<<endl;
it[ind3]=val;
for(int i=ind3/ss;i<=(n-1)/ss;i++){
if(i==ind3/ss){
for(int j=ind3+1;j<min(n,(i+1)*ss);j++){
/*if(j/ss>i){
break;
}*/
if(it[j]>=l and it[j]<=r){
update(0,0,n+q-1,ind2[j],ind2[j],cc);
}
}
//for each index check individually and update
}
else{
pair<int,int> kc={l,0};
int low=lower_bound(tt[i].begin(),tt[i].end(),kc)-tt[i].begin();
if(low==tt[i].size()){
continue;
}
kc.a=r+1;
int rr=lower_bound(tt[i].begin(),tt[i].end(),kc)-tt[i].begin();
if(rr==low){
continue;
}
update(0,0,n+q-1,ind[tt[i][low].b],ind[tt[i][low].b]+rr-low-1,cc);
//binary search to find index in each block and update in seg tree
}
}
ans.pb(tree4[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;
}*/
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:237:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(low==tt[i].size()){
~~~^~~~~~~~~~~~~~
bubblesort2.cpp:201:7: warning: unused variable 'kk' [-Wunused-variable]
int kk=0;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
188668 KB |
Output is correct |
| 2 |
Correct |
193 ms |
188920 KB |
Output is correct |
| 3 |
Correct |
215 ms |
190188 KB |
Output is correct |
| 4 |
Incorrect |
236 ms |
190072 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
188668 KB |
Output is correct |
| 2 |
Correct |
193 ms |
188920 KB |
Output is correct |
| 3 |
Correct |
215 ms |
190188 KB |
Output is correct |
| 4 |
Incorrect |
236 ms |
190072 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
404 ms |
218872 KB |
Output is correct |
| 2 |
Incorrect |
2224 ms |
235496 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
188668 KB |
Output is correct |
| 2 |
Correct |
193 ms |
188920 KB |
Output is correct |
| 3 |
Correct |
215 ms |
190188 KB |
Output is correct |
| 4 |
Incorrect |
236 ms |
190072 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
