Submission #225451

#	Time	Username	Problem	Language	Result	Execution time	Memory
225451		MKopchev	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2456 ms	53628 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
using namespace std;

const int nmax=2*5e5+42;

struct info
{
    int maxi,lazy;
};

info tree[4*nmax];

void push(int node)
{
    tree[node*2].lazy+=tree[node].lazy;
    tree[node*2+1].lazy+=tree[node].lazy;
    tree[node].lazy=0;
}

info actual(info ret)
{
    ret.maxi+=ret.lazy;
    ret.lazy=0;
    return ret;
}

info my_merge(info a,info b)
{
    a=actual(a);
    b=actual(b);

    if(a.maxi<b.maxi)return b;
    return a;
}
void update_single(int node,int l,int r,int pos,int val)
{
    if(l==r)
    {
        tree[node].maxi=val;
        return;
    }

    push(node);

    int av=(l+r)/2;

    if(pos<=av)update_single(node*2,l,av,pos,val);
    else update_single(node*2+1,av+1,r,pos,val);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}

void update_range(int node,int l,int r,int lq,int rq,int val)
{
    if(l==lq&&r==rq)
    {
        tree[node].lazy+=val;
        return;
    }
    push(node);

    int av=(l+r)/2;

    if(lq<=av)update_range(node*2,l,av,lq,min(av,rq),val);
    if(av<rq)update_range(node*2+1,av+1,r,max(av+1,lq),rq,val);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V)
{
    vector< pair<int,int> > active={};
    for(int i=0;i<A.size();i++)
        active.push_back({A[i],i});

    for(int i=0;i<X.size();i++)
        active.push_back({V[i],X[i]});

    sort(active.begin(),active.end());

    unique(active.begin(),active.end());

    int n=active.size()-1;

    for(int i=0;i<A.size();i++)
    {
        int pos=lower_bound(active.begin(),active.end(),make_pair(A[i],i))-active.begin();

        update_single(1,0,n,pos,i);

        if(pos+1<=n)update_range(1,0,n,pos+1,n,-1);
    }

    vector<int> output={};

    for(int i=0;i<X.size();i++)
    {
        int pos=lower_bound(active.begin(),active.end(),make_pair(A[X[i]],X[i]))-active.begin();

        update_single(1,0,n,pos,-1e9);

        if(pos+1<=n)update_range(1,0,n,pos+1,n,1);

        A[X[i]]=V[i];

        pos=lower_bound(active.begin(),active.end(),make_pair(V[i],X[i]))-active.begin();

        update_single(1,0,n,pos,X[i]);

        if(pos+1<=n)update_range(1,0,n,pos+1,n,-1);

        output.push_back(actual(tree[1]).maxi);
    }
    return output;
}
/*
int main()
{
    vector<int> A={1,2,3,4};
    vector<int> X={0,2};
    vector<int> V={3,1};

    for(auto k:countScans(A,X,V))cout<<k<<endl;

    return 0;
}
*/

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:73:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<A.size();i++)
                 ~^~~~~~~~~
bubblesort2.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<X.size();i++)
                 ~^~~~~~~~~
bubblesort2.cpp:85:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<A.size();i++)
                 ~^~~~~~~~~
bubblesort2.cpp:96:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<X.size();i++)
                 ~^~~~~~~~~

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