Submission #597539

#	Time	Username	Problem	Language	Result	Execution time	Memory
597539		urosk	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	79 ms	38484 KiB

bubblesort2

#include "bubblesort2.h"
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;

typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define maxn 2000005
ll n,q;
pll a[maxn];
ll b[maxn];
ll x[maxn];
ll v[maxn];
ll t[4*maxn];
ll lazy[4*maxn];
void push(ll v,ll tl,ll tr){
    t[v]+=lazy[v];
    if(tl<tr){
        lazy[2*v]+=lazy[v];
        lazy[2*v+1]+=lazy[v];
    }
    lazy[v] = 0;
}
void upd(ll v,ll tl,ll tr,ll l,ll r,ll x){
    push(v,tl,tr);
    if(l>r) return;
    if(tl==l&&tr==r){
        lazy[v]+=x;
        push(v,tl,tr);
        return;
    }
    ll mid = (tl+tr)/2;
    upd(2*v,tl,mid,l,min(mid,r),x);
    upd(2*v+1,mid+1,tr,max(mid+1,l),r,x);
    t[v] = max(t[2*v],t[2*v+1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r){
    push(v,tl,tr);
    if(l>r) return 0;
    if(tl==l&&tr==r) return t[v];
    ll mid = (tl+tr)/2;
    return max(get(2*v,tl,mid,l,min(mid,r)),get(2*v+1,mid+1,tr,max(mid+1,l),r));
}
void init(ll v,ll tl,ll tr){
    if(tl==tr){
        t[v] = b[tl];
        return;
    }
    ll mid = (tl+tr)/2;
    init(2*v,tl,mid);
    init(2*v+1,mid+1,tr);
    t[v] = max(t[2*v],t[2*v+1]);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	n = sz(A);
	q = sz(X);
	set<pll> s;
	map<pll,ll> mp;
    for(ll i = 1;i<=n;i++) a[i] = {A[i-1],i};
    for(ll i = 1;i<=q;i++) x[i] = X[i-1]+1;
    for(ll i = 1;i<=q;i++) v[i] = V[i-1];
    for(ll i = 1;i<=n;i++) s.insert(a[i]);
    for(ll i = 1;i<=q;i++) s.insert({v[i],x[i]});
    ll it = 1;
    ll m = it-1;
    ll mx = maxn-5;
    for(pll p : s) mp[p] = it++;
    for(ll i = 1;i<=n;i++) a[i].fi = mp[a[i]];
    for(ll i = 1;i<=n;i++) b[a[i].fi] = i;
    for(ll i = 1;i<=q;i++) v[i] = mp[{v[i],x[i]}];
    init(1,1,mx);
    for(ll i = 1;i<=n;i++) upd(1,1,mx,a[i].fi+1,mx,-1);
    vector<int> ans;
    for(ll j = 1;j<=q;j++){
        ll i = x[j];
        ll val = v[j];
        ll z = a[i].fi;
        upd(1,1,mx,z+1,mx,1);
        upd(1,1,mx,z,z,-i);
        upd(1,1,mx,val,val,i);
        upd(1,1,mx,val+1,mx,-1);
        ans.pb(t[1]-1);
    }
    return ans;
}
/*
4 2
1 2 3 4
0 3
2 1
*/

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:82:8: warning: unused variable 'm' [-Wunused-variable]
   82 |     ll m = it-1;
      |        ^

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