| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 962610 | pcc | 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 "bubblesort2.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
typedef tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int mxn = 5e5+10;
const int inf = 1e9+10;
vector<int> ans;
struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
struct node{
int mx,smx,tag;
node(){
mx = inf;
smx = 0;
tag = 0;
}
};
node seg[mxn*4];
SEG(){
for(auto &i:seg)i = node();
}
void push(int now){
if(seg[ls].mx >= seg[now].mx)seg[ls].tag += seg[now].tag,seg[ls].mx = seg[now].mx;
if(seg[rs].mx >= seg[now].mx)seg[rs].tag += seg[now].tag,seg[rs].mx = seg[now].mx;
seg[now].tag = 0;
return;
}
void pull(int now){
seg[now].mx = max(seg[ls].mx,seg[rs].mx);
if(seg[ls].mx<seg[rs].mx)seg[now].smx = max(seg[ls].mx,seg[rs].smx);
else if(seg[ls].mx>seg[rs].mx)seg[now].smx = max(seg[ls].smx,seg[rs].mx);
else seg[now].smx = max(seg[ls].smx,seg[rs].smx);
return;
}
void modify(int now,int l,int r,int s,int e,int v){
if(seg[now].mx<v)return;
if(l>=s&&e>=r){
if(seg[now].smx<v){
seg[now].mx = v;
seg[now].tag++;
}
else{
push(now);
modify(ls,l,mid,s,e,v);
modify(rs,mid+1,r,s,e,v);
pull(now);
}
return;
}
push(now);
if(mid>=s)modify(ls,l,mid,s,e,v);
if(mid<e)modify(rs,mid+1,r,s,e,v);
pull(now);
}
void dfs(int now,int l,int r){
if(l == r){
ans.push_back(seg[now].tag);
return;
}
push(now);
dfs(ls,l,mid);
dfs(rs,mid+1,r);
pull(now);
return;
}
#undef ls
#undef rs
#undef mid
};
SEG seg;
vector<pii> op[mxn];
int N,Q;
void bubble(vector<int> &v){
for(int i = 0;i+1<v.size();i++){
if(v[i]>v[i+1])swap(v[i],v[i+1]);
}
return;
}
bool sorted(vector<int> &v){
for(int i = 0;i+1<v.size();i++){
if(v[i]>v[i+1])return false;
}
return true;
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
N = A.size(),Q = X.size();
ordered_set st;
for(int i = 0;i<Q;i++){
int p = X[i],v = V[i];
ans.push_back(0);
st.clear();
for(int j = 0;j<N;j++){
ans.back() = max(ans.back(),st.size()-st.order_of_key(pii(A[j],j)));
st.insert(pii(A[j],j));
}
/*
int tans = 0,sm = inf;
for(int j = N-1;j>=0;j--){
tans += (sm>=A[j]);
sm = min(sm,A[j]);
}
ans.push_back(N-tans);
*/
}
return ans;
for(int i = 0;i<N;i++)op[i].push_back(pii(0,A[i]));
for(int i = 0;i<Q;i++){
int p = X[i],v = V[i];
op[p].push_back(pii(i+1,v));
}
for(int i = N-1;i>=0;i--){
int pre = Q;
while(!op[i].empty()){
auto [t,v] = op[i].back();op[i].pop_back();
seg.modify(0,0,Q,t,pre,v);
pre = t-1;
}
}
seg.dfs(0,0,Q);
ans.erase(ans.begin());
for(auto &i:ans)i = N-i;
return ans;
}