Submission #787795

#	Time	Username	Problem	Language	Result	Execution time	Memory
787795		Rafi22	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2795 ms	160604 KiB

bubblesort2

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int N=500007,pot=1<<20;

map<int,int>id[N];

int lzy[2*pot+7];
int seg[2*pot+7];

void push(int v)
{
    lzy[2*v]+=lzy[v];
    seg[2*v]+=lzy[v];
    lzy[2*v+1]+=lzy[v];
    seg[2*v+1]+=lzy[v];
    lzy[v]=0;
}

void ins(int v,int a,int b,int l,int r,int x)
{
    if(a<=l&&b>=r)
    {
        seg[v]+=x;
        lzy[v]+=x;
        return ;
    }
    if(r<a||l>b) return ;
    push(v);
    ins(2*v,a,b,l,(l+r)/2,x);
    ins(2*v+1,a,b,(l+r)/2+1,r,x);
    seg[v]=max(seg[2*v],seg[2*v+1]);
}

vector<int>countScans(vector<int>a,vector<int>X,vector<int>V)
{
    set<pair<int,int>>S;
    int n=sz(a),q=sz(X);
    for(int i=0;i<n;i++) S.insert({a[i],i});
    for(int i=0;i<q;i++) S.insert({V[i],X[i]});
    int it=0;
    for(int i=1;i<=pot;i++) seg[i+pot-1]=-inf;
    for(auto x:S)
    {
        id[x.nd][x.st]=++it;
        seg[it+pot-1]+=x.nd;
    }
    for(int i=0;i<n;i++) seg[id[i][a[i]]+pot-1]+=inf;
    for(int i=pot-1;i>0;i--) seg[i]=max(seg[2*i],seg[2*i+1]);
    for(int i=0;i<n;i++) ins(1,id[i][a[i]]+1,pot,1,pot,-1);
    vector<int>ans(q);
    for(int i=0;i<q;i++)
    {
        ins(1,id[X[i]][a[X[i]]]+1,pot,1,pot,1);
        ins(1,id[X[i]][a[X[i]]],id[X[i]][a[X[i]]],1,pot,-inf);
        a[X[i]]=V[i];
        ins(1,id[X[i]][a[X[i]]],id[X[i]][a[X[i]]],1,pot,inf);
        ins(1,id[X[i]][a[X[i]]]+1,pot,1,pot,-1);
        ans[i]=seg[1];
    }
    return ans;
}

/*int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    vector<int>X=countScans({1,2, 3, 4},{0, 2},{3, 1});
    for(auto x:X) cout<<x<<" ";




    return 0;
}*/

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