| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 199384 | mahmoudbadawy | Bubble Sort 2 (JOI18_bubblesort2) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
struct node
{
pair<int,int> val;
int prio,maxi,lazy,mv,co;
node* pa;
node* l; node* r;
node():val(make_pair(0,0)),prio(rand()),l(0),r(0),pa(0),lazy(0),maxi(0),mv(0),co(0){}
node(pair<int,int> val,int mv):val(val),mv(mv),prio(rand()),l(0),r(0),pa(0),lazy(0),co(1){}
};
int getco(node* n)
{
if(!n) return 0;
return n->co;
}
void update(node* &x)
{
if(x)
{
x->mv+=x->lazy;
x->maxi=x->mv;
x->co=1;
if(x->l)
{
x->l->maxi+=x->lazy; x->l->lazy+=x->lazy;
x->maxi=max(x->maxi,x->l->maxi);
x->co+=x->l->co;
}
if(x->r)
{
x->r->maxi+=x->lazy; x->r->lazy+=x->lazy;
x->maxi=max(x->maxi,x->r->maxi);
x->co+=x->r->co;
}
x->lazy=0;
}
}
void split(node *root,node* &l,node* &r,pair<int,int> ind,node* lpa=0,node* rpa=0)
{
if(root==0)
{
l=r=0; return;
}
if(ind<root->val)
{
r=root;
split(root->l,l,r->l,ind,lpa,r);
if(r) r->pa=rpa;
update(r);
}
else
{
l=root;
split(root->r,l->r,r,ind,l,rpa);
if(l) l->pa=lpa;
update(l);
}
update(root);
}
void merge(node* &root,node* l,node *r,node* pa=0)
{
if(l==0)
{
root=r;
}
else if(r==0)
{
root=l;
}
else if(l->prio>r->prio)
{
root=l;
merge(l->r,l->r,r,root);
}
else
{
root=r;
merge(r->l,l,r->l,root);
}
if(root) root->pa=pa;
update(root);
}
void insert(node* &root,node* cur,pair<int,int> val)
{
node* l1; node* l2;
split(root,l1,l2,val);
merge(root,l1,cur); merge(root,root,l2);
}
const int N=1e5+5;
node* root;
int n,q;
void print(node * root,int dep=0){
if(root){
cout << string(dep,' ');
printf("%d %d\n ", (root->val).first, root->co);
print(root->l,dep+1);
print(root->r,dep+1);
}
}
void modify(int ox,int nx,int i)
{
node *a,*x,*y,*b;
// update the value
split(root,a,x,{ox,i-1});
split(x,y,b,{ox,i});
y->val={nx,i};
// update the numeber of moves
if(nx>ox)
{
split(b,x,b,{nx,i});
// a x y b
y->mv=i/2-(getco(a)+getco(x));
if(x) {x->lazy+=1; update(x);}
merge(root,a,x);
merge(root,root,y);
merge(root,root,b);
}
else
{
merge(b,x,b);
split(a,a,x,{nx,i});
// a y x b
y->mv=i/2-getco(a);
if(x) {x->lazy-=1; update(x);}
merge(root,a,y);
merge(root,root,b);
}
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
n=A.size(),q=X.size();
vector<pair<int,int> > v;
for(int i=0;i<A.size();i++)
v.push_back({A[i],2*i});
sort(v.begin(),v.end());
for(int i=0;i<n;i++)
{
node* cur=new node(v[i],v[i].second/2-i);
insert(root,cur,v[i]);
}
//print(root);
vector<int> ans;
for(int i=0;i<q;i++)
{
if(A[X[i]]!=V[i])
modify(A[X[i]],V[i],2*X[i]);
A[X[i]]=V[i];
ans.push_back(root->maxi);
//cout << (root->maxi) << endl;
//print(root);
}
return ans;
}
#include <cstdio>
#include <cstdlib>
#include <vector>
int readInt(){
int i;
if(scanf("%d",&i)!=1){
fprintf(stderr,"Error while reading input\n");
exit(1);
}
return i;
}
int main(){
int N,Q;
N=readInt();
Q=readInt();
std::vector<int> A(N);
for(int i=0;i<N;i++)
A[i]=readInt();
std::vector<int> X(Q),V(Q);
for(int j=0;j<Q;j++){
X[j]=readInt();
V[j]=readInt();
}
std::vector<int> res=countScans(A,X,V);
for(int j=0;j<int(res.size());j++)
printf("%d\n",res[j]);
return 0;
}