Submission #513760

#	Time	Username	Problem	Language	Result	Execution time	Memory
513760		andrei_boaca	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	5187 ms	168512 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
//#include "grader.cpp"
using namespace std;
const int INF=1e9;
typedef pair<int,int> pii;
map<pii,int> nrm;
int arb[4000005],toprop[4000005];
int q,n;
vector<pii> query;
vector<int> v;
set<pii> s;
int nr=0;
void prop(int nod)
{
    int val=toprop[nod];
    for(int i=nod*2;i<=nod*2+1;i++)
    {
        arb[i]+=val;
        toprop[i]+=val;
    }
}
void update(int nod,int st,int dr,int a,int b,int val)
{
    if(toprop[nod]!=0&&st!=dr)
        prop(nod);
    toprop[nod]=0;
    if(st>=a&&dr<=b)
    {
        arb[nod]+=val;
        toprop[nod]+=val;
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        update(nod*2,st,mij,a,b,val);
    if(b>mij)
        update(nod*2+1,mij+1,dr,a,b,val);
    arb[nod]=max(arb[nod*2],arb[nod*2+1]);
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V)
{
    vector<int> sol;
    q=X.size();
    n=A.size();
    for(int i=0;i<q;i++)
        query.push_back({X[i],V[i]});
    v=A;
    for(int i=0;i<q;i++)
        s.insert({V[i],X[i]});
    for(int i=0;i<n;i++)
        s.insert({v[i],i});
    for(pii i:s)
    {
        nr++;
        nrm[i]=nr;
    }
    for(int i=1;i<=4*nr;i++)
        arb[i]=-INF;
    for(int i=0;i<n;i++)
    {
        int poz=nrm[{v[i],i}];
        update(1,1,nr,poz,poz,+INF);
        update(1,1,nr,poz,nr,-1);
        update(1,1,nr,poz,poz,i+1);
    }
    for(int j=0;j<q;j++)
    {
        int poz;
        int p=X[j];
        poz=nrm[{v[p],p}];
        update(1,1,nr,poz,poz,-(p+1));
        update(1,1,nr,poz,nr,+1);
        update(1,1,nr,poz,poz,-INF);

        v[p]=V[j];
        poz=nrm[{v[p],p}];
        update(1,1,nr,poz,poz,(p+1));
        update(1,1,nr,poz,nr,-1);
        update(1,1,nr,poz,poz,+INF);

        sol.push_back(arb[1]);
    }
    return sol;
}

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