| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 66172 | reality | 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"
using namespace std;
#define fi first
#define se second
#define ll long long
#define dbg(v) cerr<<#v<<" = "<<v<<'\n'
#define vi vector<int>
#define vl vector <ll>
#define pii pair<int,int>
#define mp make_pair
#define db long double
#define pb push_back
#define all(s) s.begin(),s.end()
template < class P , class Q > ostream& operator<<(ostream& stream, pair < P , Q > v){ stream << "(" << v.fi << ',' << v.se << ")"; return stream;}
template < class T > ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream;}
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
const int oo = 1e9;
const int N = 4e6 + 5;
int s[N];
int p[N];
int q[N];
int t[N];
int ok[N];
int lz[N];
int get(int node) {
if (ok[node])
return t[node];
return 0;
}
void upd(int node) {
ok[node] = ok[node * 2] + ok[node * 2 + 1];
t[node] = max(get(node * 2),get(node * 2 + 1));
}
void upd_lz(int l,int r,int node) {
if (!lz[node])
return;
if (l != r)
lz[node * 2] += lz[node],
lz[node * 2 + 1] += lz[node];
t[node] += lz[node];
lz[node] = 0;
return;
}
vector< pii > w;
void build(int l,int r,int node) {
if (l == r) {
t[node] = w[l - 1].se;
} else {
int m = (l + r) / 2;
build(l,m,node * 2);
build(m+1,r,node * 2 + 1);
}
}
void Update1(int l,int r,int pos,int node) {
upd_lz(l,r,node);
if (l == r) {
ok[node] ^= 1;
}
else {
int m = (l + r) / 2;
if (pos <= m)
Update1(l,m,pos,node * 2),upd_lz(m+1,r,node * 2 + 1);
else
Update1(m+1,r,pos,node * 2 + 1),upd_lz(l,m,node * 2);
upd(node);
}
}
void Update2(int l,int r,int l1,int r1,int v,int node) {
upd_lz(l,r,node);
if (l1 <= l && r <= r1)
lz[node] += v,upd_lz(l,r,node);
else {
int m = (l + r) / 2;
if (l1 <= m)
Update2(l,m,l1,r1,v,node * 2);
else
upd_lz(l,m,node * 2);
if (m+1<=r1)
Update2(m+1,r,l1,r1,v,node * 2 + 1);
upd(node);
}
}
int query(int l,int r,int l1,int r1,int node) {
upd_lz(l,r,node);
if (l1 <= l && r <= r1)
return get(node);
int m = (l + r) / 2;
int ans = 0;
if (l1 <= m)
smax(ans,query(l,m,l1,r1,node * 2));
else
upd_lz(l,m,node * 2);
if (m+1<=r1)
smax(ans,query(m+1,r,l1,r1,node * 2 + 1));
else
upd_lz(m+1,r,node * 2 + 1);
upd(node);
return ans;
}
void print(int l,int r,int node) {
upd_lz(l,r,node);
if (l != r) {
int m = (l + r) / 2;
print(l,m,node * 2);
print(m+1,r,node * 2 + 1);
} else {
dbg((vi{l,get(node),w[l - 1].fi,w[l - 1].se,ok[node]}));
}
//dbg((vi{l,r,node,t[node],ok[node]}));
}
vi count_scans(vi S1,vi S2,vi S3){
int n = S1.size();
for (int i = 0;i < n;++i)
w.pb(mp(S1[i],i + 1));
for (int i = 0;i < S2.size();++i)
w.pb(mp(S3[i],S2[i] + 1));
sort(all(w));
w.resize(unique(all(w)) - w.begin());
const int SZ = w.size();
vector < pii > qq;
for (int i = 0;i < S2.size();++i)
qq.pb(mp(S3[i],S2[i] + 1));
for (int i = 0;i < n;++i)
s[i + 1] = S1[i];
vi answer;
build(1,SZ,1);
for (int i = 1;i <= n;++i) {
int Who = lower_bound(all(w),mp(s[i],i)) - w.begin() + 1;
Update1(1,SZ,Who,1);
Update2(1,SZ,Who,SZ,-1,1);
}
for (auto it : qq) {
int Who = lower_bound(all(w),it) - w.begin() + 1;
int Del = lower_bound(all(w),mp(s[it.se],it.se)) - w.begin() + 1;
Update1(1,SZ,Del,1);
Update2(1,SZ,Del,SZ,1,1);
Update1(1,SZ,Who,1);
Update2(1,SZ,Who,SZ,-1,1);
answer.pb(t[1]);
s[it.se] = it.fi;
}
return answer;
}