#include "bubblesort2.h"
#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){ return;
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,x);
}
}
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]);
}
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);
}
return ans;
}
Compilation message
bubblesort2.cpp:4:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("O3")
bubblesort2.cpp:5:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
#pragma GCC optimization ("unroll-loops")
bubblesort2.cpp: In constructor 'node::node()':
bubblesort2.cpp:15:17: warning: 'node::r' will be initialized after [-Wreorder]
node* l; node* r;
^
bubblesort2.cpp:14:8: warning: 'node* node::pa' [-Wreorder]
node* pa;
^~
bubblesort2.cpp:16:2: warning: when initialized here [-Wreorder]
node():val(make_pair(0,0)),prio(rand()),l(0),r(0),pa(0),lazy(0),maxi(0),mv(0),co(0){}
^~~~
bubblesort2.cpp:14:8: warning: 'node::pa' will be initialized after [-Wreorder]
node* pa;
^~
bubblesort2.cpp:13:16: warning: 'int node::lazy' [-Wreorder]
int prio,maxi,lazy,mv,co;
^~~~
bubblesort2.cpp:16:2: warning: when initialized here [-Wreorder]
node():val(make_pair(0,0)),prio(rand()),l(0),r(0),pa(0),lazy(0),maxi(0),mv(0),co(0){}
^~~~
bubblesort2.cpp:13:16: warning: 'node::lazy' will be initialized after [-Wreorder]
int prio,maxi,lazy,mv,co;
^~~~
bubblesort2.cpp:13:11: warning: 'int node::maxi' [-Wreorder]
int prio,maxi,lazy,mv,co;
^~~~
bubblesort2.cpp:16:2: warning: when initialized here [-Wreorder]
node():val(make_pair(0,0)),prio(rand()),l(0),r(0),pa(0),lazy(0),maxi(0),mv(0),co(0){}
^~~~
bubblesort2.cpp: In constructor 'node::node(std::pair<int, int>, int)':
bubblesort2.cpp:13:21: warning: 'node::mv' will be initialized after [-Wreorder]
int prio,maxi,lazy,mv,co;
^~
bubblesort2.cpp:13:6: warning: 'int node::prio' [-Wreorder]
int prio,maxi,lazy,mv,co;
^~~~
bubblesort2.cpp:17:2: warning: when initialized here [-Wreorder]
node(pair<int,int> val,int mv):val(val),mv(mv),prio(rand()),l(0),r(0),pa(0),lazy(0),co(1){}
^~~~
bubblesort2.cpp:15:17: warning: 'node::r' will be initialized after [-Wreorder]
node* l; node* r;
^
bubblesort2.cpp:14:8: warning: 'node* node::pa' [-Wreorder]
node* pa;
^~
bubblesort2.cpp:17:2: warning: when initialized here [-Wreorder]
node(pair<int,int> val,int mv):val(val),mv(mv),prio(rand()),l(0),r(0),pa(0),lazy(0),co(1){}
^~~~
bubblesort2.cpp:14:8: warning: 'node::pa' will be initialized after [-Wreorder]
node* pa;
^~
bubblesort2.cpp:13:16: warning: 'int node::lazy' [-Wreorder]
int prio,maxi,lazy,mv,co;
^~~~
bubblesort2.cpp:17:2: warning: when initialized here [-Wreorder]
node(pair<int,int> val,int mv):val(val),mv(mv),prio(rand()),l(0),r(0),pa(0),lazy(0),co(1){}
^~~~
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:152:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<A.size();i++)
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
29 ms |
4852 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
