Submission #367913

#	Time	Username	Problem	Language	Result	Execution time	Memory
367913		denkendoemeer	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	26 ms	1516 KiB

bubblesort2

#include<bits/stdc++.h>
#include "bubblesort2.h"
#define ll long long
using namespace std;
int offset[1000005],f[1000005],val[1000005],aint[4000005],lazy[4000005];
vector<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]);
}
void add(int poz,int nr)
{
    if (val[poz]!=2e9){
        update(1,0,l-1,val[poz]+1,l-1,1);
        update2(1,0,l-1,val[poz],-poz);
    }
    val[poz]=nr;
    update(1,0,l-1,val[poz]+1,l-1,-1);
    update2(1,0,l-1,val[poz],poz);
}
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(a[i]);
    for(i=0;i<q;i++)
        aux.push_back(v[i]);
    sort(aux.begin(),aux.end());
    aux.resize(unique(aux.begin(),aux.end())-aux.begin());
    for(i=0;i<n;i++)
        a[i]=lower_bound(aux.begin(),aux.end(),a[i])-aux.begin();
    for(i=0;i<q;i++)
        v[i]=lower_bound(aux.begin(),aux.end(),v[i])-aux.begin();
    l=n+q;
    for(i=0;i<n;i++)
        offset[a[i]+1]++;
    for(i=0;i<q;i++)
        offset[v[i]+1]++;
    for(i=2;i<aux.size();i++)
        offset[i]=offset[i-1]+offset[i];
    for(i=0;i<n;i++)
        val[i]=2e9;
    for(i=0;i<n;i++)
        add(i,offset[a[i]]+f[a[i]]),f[a[i]]++;
    vector<int>ans;
    for(i=0;i<q;i++){
        add(x[i],offset[v[i]]+f[v[i]]),f[v[i]]++;
        ans.push_back(aint[1]);
    }
    return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:87:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(i=2;i<aux.size();i++)
      |             ~^~~~~~~~~~~

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