Submission #369508

#	Time	Username	Problem	Language	Result	Execution time	Memory
369508		denkendoemeer	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	3136 ms	53576 KiB

bubblesort2

#include<bits/stdc++.h>
#include "bubblesort2.h"
#define ll long long
using namespace std;
int val[1000005],aint[4000005],lazy[4000005];
vector<pair<int,int>>aux;
int n,q,l;
void push(int nod,int st,int dr)
{
    if (lazy[nod]){
        aint[nod]+=lazy[nod];
        if (st!=dr){
            lazy[nod*2]+=lazy[nod];
            lazy[nod*2+1]+=lazy[nod];
        }
        lazy[nod]=0;
    }
}
void update(int nod,int st,int dr,int l,int r,int add)
{
    if (l>r)
        return ;
    if (l<=st && dr<=r){
        aint[nod]+=add;
        if (st!=dr){
            lazy[nod*2]+=add;
            lazy[nod*2+1]+=add;
        }
        return ;
    }
    push(nod,st,dr);
    int mij=(st+dr)/2;
    if (l<=mij)
        update(nod*2,st,mij,l,r,add);
    if (mij+1<=r)
        update(nod*2+1,mij+1,dr,l,r,add);
    push(nod*2,st,mij);
    push(nod*2+1,mij+1,dr);
    aint[nod]=max(aint[nod*2],aint[nod*2+1]);
}
void update2(int nod,int st,int dr,int poz,int val)
{
    if (st==dr){
        aint[nod]+=val;
        return ;
    }
    push(nod,st,dr);
    int mij=(st+dr)/2;
    if (poz<=mij)
        update2(nod*2,st,mij,poz,val);
    else
        update2(nod*2+1,mij+1,dr,poz,val);
    push(nod*2,st,mij);
    push(nod*2+1,mij+1,dr);
    aint[nod]=max(aint[nod*2],aint[nod*2+1]);
}
int calcpoz(pair<int,int>auxi)
{
    return lower_bound(aux.begin(),aux.end(),auxi)-aux.begin();
}
vector<int> countScans(vector<int>a,vector<int>x,vector<int>v)
{
    n=a.size();
    q=x.size();
    int i;
    for(i=0;i<n;i++)
        aux.push_back(make_pair(a[i],i));
    for(i=0;i<q;i++)
        aux.push_back(make_pair(v[i],x[i]));
    sort(aux.begin(),aux.end());
    aux.resize(unique(aux.begin(),aux.end())-aux.begin());
    for(i=0;i<n;i++){
        int ind1=calcpoz(make_pair(a[i],i));
        update(1,0,aux.size()-1,ind1,ind1,(i+1));
		int ind2=calcpoz(make_pair(a[i],-1));
		update(1,0,aux.size()-1,ind2,aux.size()-1,-1);
    }
    vector<int>ans;
    for(i=0;i<q;i++){
        int ind1=calcpoz(make_pair(a[x[i]],x[i]));
        update(1,0,aux.size()-1,ind1,ind1,-(x[i]+1));
		int ind2=calcpoz(make_pair(a[x[i]],-1));
		update(1,0,aux.size()-1,ind2,aux.size()-1,1);
        a[x[i]]=v[i];
        ind1=calcpoz(make_pair(a[x[i]],x[i]));
        update(1,0,aux.size()-1,ind1,ind1,(x[i]+1));
		ind2=calcpoz(make_pair(a[x[i]],-1));
		update(1,0,aux.size()-1,ind2,aux.size()-1,-1);
        ans.push_back(aint[1]);
    }
    return ans;
}

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