Submission #1270925

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270925		_kani	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	3943 ms	108928 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"

#define ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define F "TASK"
#define fio freopen(F".INP","r",stdin);freopen(F".OUT","w",stdout);

#ifdef NCGM
#include"debug.h"
#else
#define debug(...) "fr";
#endif

using namespace std;

const int N=5e5+3;

int n,a[N],b[N],sf[N];
int st[10*N],lazy[10*N],fw[N*10];
map<pair<int,int>,int> mp;
vector<pair<int,int>> vt;

void upd(int x,int y) {
    while(x<=sz(vt)) {
        fw[x]+=y;
        x+=x&(-x);
    }
}
int qr(int x) {
    int ans=0;
    while(x>0) {
        ans+=fw[x];
        x-=x&(-x);
    }
    return ans;
}

void push(int id) {
    st[id*2]+=lazy[id];
    st[id*2+1]+=lazy[id];
    lazy[id*2]+=lazy[id];
    lazy[id*2+1]+=lazy[id];
    lazy[id]=0;
}
void build(int id,int l,int r) {
    st[id]=-2e9;
    if (l==r) return;
    int mid=l+r>>1;
    build(id*2,l,mid);
    build(id*2+1,mid+1,r);
}
void update(int id,int l,int r,int u,int v,int x) {
    if (l>v || r<u) return;
    if (l>=u && r<=v) {
        st[id]+=x;
        lazy[id]+=x;
        return;
    }
    push(id);
    int mid=l+r>>1;
    update(id*2,l,mid,u,v,x);
    update(id*2+1,mid+1,r,u,v,x);
    st[id]=max(st[id*2],st[id*2+1]);
}
void update1(int id,int l,int r,int u,int x) {
    if (l>u || r<u) return;
    if (l==r) {
        st[id]=x;
        return;
    }
    push(id);
    int mid=l+r>>1;
    update1(id*2,l,mid,u,x);
    update1(id*2+1,mid+1,r,u,x);
    st[id]=max(st[id*2],st[id*2+1]);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V) {
    n=sz(A);
    vector<int> res;
    For(i,1,n) a[i]=A[i-1];
    For(i,1,n) vt.pb({a[i],i});
    For(i,0,sz(X)-1) {
        int x=X[i],v=V[i];
        x++;
        vt.pb({v,x});
    }
    sort(all(vt));
    unq(vt);
    For(i,0,sz(vt)-1) mp[vt[i]]=i+1;
    For(i,1,n) {
        int id=mp[{a[i],i}];
        upd(id,1);
    }
    build(1,1,sz(vt));
    For(i,1,n) {
        int id=mp[{a[i],i}];
        update1(1,1,sz(vt),id,i-qr(id));
    }
    For(i,0,sz(X)-1) {
        int x=X[i],v=V[i];
        x++;
        int id=mp[{v,x}];
        int id1=mp[{a[x],x}];
        upd(id1,-1);
        update1(1,1,sz(vt),id1,-2e9);
        a[x]=v;
       // if (i==0) cout << id1 << " " << id << endl;
        upd(id,1);
        if (id1<id) update(1,1,sz(vt),id1,id-1,1);
        else if (id<id1)  update(1,1,sz(vt),id,id1-1,-1);
        update1(1,1,sz(vt),id,x-qr(id));
        res.pb(st[1]);
    }
   // for(auto x: vt) cout << x.ff << " " << x.ss << endl;
    //cout << st[1] << endl;

    return res;
}

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