Submission #1286493

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286493		StefanSebez	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	2847 ms	121816 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e6+50,inf=1e9;
void Unique(vector<int>&a){sort(a.begin(),a.end());a.resize(unique(a.begin(),a.end())-a.begin());}
int n,q,a[N];
set<int>st[N];
struct SegTree{
    int root,nc,lc[2*N],rc[2*N],maks[2*N],lazy[2*N];
    SegTree(){maks[0]=-inf;}
    void update(int &c,int x){if(!c)c=++nc;maks[c]+=x;lazy[c]+=x;}
    void push(int &c){if(!c)c=++nc;update(lc[c],lazy[c]);update(rc[c],lazy[c]);lazy[c]=0;}
    void Update(int &c,int ss,int se,int qs,int qe,int x){
        if(!c)c=++nc;
        if(qs>qe||qe<ss||se<qs)return;
        if(qs<=ss&&se<=qe){update(c,x);return;}
        int mid=ss+se>>1;push(c);
        Update(lc[c],ss,mid,qs,qe,x);Update(rc[c],mid+1,se,qs,qe,x);
        maks[c]=max(maks[lc[c]],maks[rc[c]]);
    }
    int Get(int &c,int ss,int se,int qs,int qe){
        if(!c)c=++nc;
        if(qs>qe||qe<ss||se<qs)return -inf;
        if(qs<=ss&&se<=qe)return maks[c];
        int mid=ss+se>>1;push(c);
        return max(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
    }
}ST;
vector<int> countScans(vector<int>A,vector<int> X,vector<int> V){
	n=A.size();q=X.size();
	for(int i=1;i<=n;i++) a[i]=A[i-1];
	for(auto &i:X) i++;
	vector<int>vals;
	for(int i=1;i<=n;i++) vals.pb(a[i]);
	for(auto i:V) vals.pb(i);
	Unique(vals);
	for(int i=1;i<=n;i++) a[i]=lower_bound(vals.begin(),vals.end(),a[i])-vals.begin();
	for(auto &i:V) i=lower_bound(vals.begin(),vals.end(),i)-vals.begin();

	vector<int>res(q,0);
	for(int i=1;i<=n;i++){
        if(!st[a[i]].empty()){
            ST.Update(ST.root,0,N,a[i],a[i],-*st[a[i]].rbegin());
        }
        st[a[i]].insert(i);
        ST.Update(ST.root,0,N,a[i],a[i],*st[a[i]].rbegin());
        ST.Update(ST.root,0,N,a[i],N,-1);
	}
	for(int I=0;I<q;I++){
        int j=X[I];
        ST.Update(ST.root,0,N,a[j],N,1);
        ST.Update(ST.root,0,N,a[j],a[j],-*st[a[j]].rbegin());
        st[a[j]].erase(j);
        if(!st[a[j]].empty())ST.Update(ST.root,0,N,a[j],a[j],*st[a[j]].rbegin());
        a[j]=V[I];
        if(!st[a[j]].empty())ST.Update(ST.root,0,N,a[j],a[j],-*st[a[j]].rbegin());
        st[a[j]].insert(j);
        ST.Update(ST.root,0,N,a[j],a[j],*st[a[j]].rbegin());
        ST.Update(ST.root,0,N,a[j],N,-1);
        res[I]=ST.maks[ST.root];
	}
	return res;
}

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