Submission #601341

#	Time	Username	Problem	Language	Result	Execution time	Memory
601341		Iwanttobreakfree	Bubble Sort 2 (JOI18_bubblesort2)	C++98	0 / 100	9030 ms	1492 KiB

bubblesort2

#include <iostream>
#include <vector>
#include <map>
#include "bubblesort2.h"
using namespace std;
int find_min(int n,int l,int r,vector<int>& t,int x){
    if(t[n]>=x)return -1;
    if(l==r)return l;
    int mid=(r+l)/2;
    int ans=find_min((n<<1)+1,mid+1,r,t,x);
    if(ans!=-1)return ans;
    return find_min(n<<1,l,mid,t,x);
}
void p_upd(int n,int l,int r,vector<int>& t,int a,int x){
   // cout<<l<<' '<<r<<' '<<x<<'\n';
    if(l>a||r<a)return;
    if(l==r&&l==a)t[n]=x;
    else{
        int mid=(r+l)/2;
        p_upd(n<<1,l,mid,t,a,x);
        p_upd((n<<1)+1,mid+1,r,t,a,x);
        t[n]=max(t[n<<1],t[(n<<1)+1]);
    }
}
void build(int n,int l,int r,vector<int>& t,vector<int>& li){
    if(l==r)t[n]=li[l];
    else{
        int mid=(r+l)/2;
        build(n<<1,l,mid,t,li);
        build((n<<1)+1,mid+1,r,t,li);
        t[n]=min(t[n<<1],t[(n<<1)+1]);
    }
}
void p_updminimum(int n,int l,int r,vector<int>& t,int a,int x){
    //cout<<l<<' '<<r<<' '<<a<<'\n';
    if(l>a||r<a)return;
    if(l==r&&l==a)t[n]=x;
    else{
        int mid=(r+l)/2;
        p_updminimum(n<<1,l,mid,t,a,x);
        p_updminimum((n<<1)+1,mid+1,r,t,a,x);
        t[n]=min(t[n<<1],t[(n<<1)+1]);
    }
}
int val(int n,int l,int r,vector<int>& t,int a,int b){
    if(l>b||r<a)return -1;
    if(l>=a&&r<=b)return t[n];
    int mid=(r+l)/2;
    int valls=val(n<<1,l,mid,t,a,b);
    int valrs=val((n<<1)+1,mid+1,r,t,a,b);
    return max(valls,valrs);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	int Q=X.size(),N=A.size();
	vector<int> answer(Q),li;
	map<int,int> nums;
	for(auto x:A)nums[x]++;
	for(auto x:V)nums[x]++;
	for(auto x:nums)li.push_back(x.first);
	int n=li.size();
	vector<int> t_min(4*N),t_sol(4*N);
	build(1,0,N-1,t_min,A);
	for(int i=N-1;i>=0;i--){
        int u=find_min(1,0,N-1,t_min,A[i]);
        if(i<u){
            int v=val(1,0,N-1,t_sol,i+1,u);
            //cout<<v+1<<' ';
            p_upd(1,0,N-1,t_sol,i,v+1);
        }
	}
	for(int j=0;j<Q;j++) {
		int u=find_min(1,0,N-1,t_min,V[j]);
		A[X[j]]=V[j];
		p_updminimum(1,0,N-1,t_min,X[j],V[j]);
        if(X[j]<u){
            int v=val(1,0,N-1,t_sol,X[j]+1,u);
            p_upd(1,0,N-1,t_sol,X[j],v+1);
        }
        for(int i=X[j]-1;i>=0;i--){
            int u=find_min(1,0,N-1,t_min,A[i]);
            //cout<<A[i]<<' '<<i<<' '<<u<<'\n';
            if(i<u){
                int v=val(1,0,N-1,t_sol,i+1,u);
                p_upd(1,0,N-1,t_sol,i,v+1);
            }
        }
        answer[j]=t_sol[1];
	}
	//for(int x:answer)cout<<x<<' ';
	return answer;
}
/*int main(){
    vector<int> A={1,2,3,4},X={0,2},V={3,1};
    countScans(A,X,V);
}*/

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:60:6: warning: unused variable 'n' [-Wunused-variable]
   60 |  int n=li.size();
      |      ^

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