Submission #445504

#	Time	Username	Problem	Language	Result	Execution time	Memory
445504		cpp219	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2910 ms	129652 KiB

bubblesort2

#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e6 + 9;
const ll Log2 = 20;
const ll inf = 1e9 + 7;

set<ll> s[N];
ll n,Q,st[4*N],a[N],cnt[N],sz = N - 1,lazy[4*N];

void Pass(ll id){
    ll t = lazy[id]; lazy[id] = 0;
    st[id*2] += t; lazy[id*2] += t;
    st[id*2 + 1] += t; lazy[id*2 + 1] += t;
}

void upd(ll id,ll l,ll r,ll u,ll v,ll val){
    if (v < l||r < u) return;
    if (u <= l&&r <= v){
        if (u == v) st[id] = val;
        else st[id] += val,lazy[id] += val;
        return;
    }
    ll mid = (l + r)/2; Pass(id);
    upd(id*2,l,mid,u,v,val); upd(id*2 + 1,mid + 1,r,u,v,val);
    st[id] = max(st[id*2],st[id*2 + 1]);
}

vector<ll> v;
LL q[N];

ll Find(ll x){
    return lower_bound(v.begin(),v.end(),x) - v.begin() + 1;
}

void compress(){
    sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end()) - v.begin());
    for (ll i = 1;i <= n;i++) a[i] = Find(a[i]);
    for (ll i = 1;i <= Q;i++) q[i].sc = Find(q[i].sc);
}

ll bit[N];
void updBIT(ll p,ll val){
    for (ll i = p;i < N;i += i & -i) bit[i] += val;
}

ll Get(ll p){
    ll res = 0;
    for (ll i = p;i > 0;i -= i & -i) res += bit[i];
    return res;
}

void Reupdate(ll p){
    if (s[p].empty()) upd(1,1,sz,p,p,-inf);
    else{
        ll mx = *s[p].rbegin(); upd(1,1,sz,p,p,mx - Get(p));
    }
}

vector<ll> countScans(vector<ll> A,vector<ll> X,vector<ll> V){
    vector<ll> ans; ll kq;
    n = A.size(); Q = X.size();
    for (ll i = 1;i <= Q;i++){
        q[i] = {X[i - 1] + 1,V[i - 1]}; v.push_back(V[i - 1]);
    }
    for (ll i = 1;i <= n;i++) a[i] = A[i - 1],v.push_back(a[i]);
    compress();
    for (ll i = 1;i <= n;i++) s[a[i]].insert(i),updBIT(a[i],1);
    for (ll i = 1;i <= n;i++) Reupdate(a[i]);

    for (ll i = 1;i <= Q;i++){
        ll p1 = a[q[i].fs],p2 = q[i].sc;
        updBIT(p1,-1); updBIT(p2,1); a[q[i].fs] = p2;
        upd(1,1,sz,p1,sz,1); upd(1,1,sz,p2,sz,-1); //cout<<p1; exit(0);
        s[p1].erase(q[i].fs); s[p2].insert(q[i].fs); Reupdate(p1); Reupdate(p2);
        //upd(1,1,sz,1,1,-inf);
        //cout<<st[1]; exit(0);
        //cout<<*s[p2].rbegin() - Get(p2); exit(0);

        ans.push_back(st[1]);
    }
    return ans;
}

Compilation message (stderr)

bubblesort2.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
bubblesort2.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
bubblesort2.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:69:24: warning: unused variable 'kq' [-Wunused-variable]
   69 |     vector<ll> ans; ll kq;
      |                        ^~

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40