Submission #601357

#	Time	Username	Problem	Language	Result	Execution time	Memory
601357		Iwanttobreakfree	Bubble Sort 2 (JOI18_bubblesort2)	C++98	0 / 100	9091 ms	1464 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&&t[n]<x)return l;
    int mid=(r+l)/2;
    if(t[(n<<1)+1]<x)return find_min((n<<1)+1,mid+1,r,t,x);
    if(t[(n<<1)]<x)return find_min(n<<1,l,mid,t,x);
    return -1;
}
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){
    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 -1e9;
    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);
	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]);
        //cout<<u<<' ';
        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);
        }
	}
	for(int j=0;j<Q;j++) {
        A[X[j]]=V[j];
		p_updminimum(1,0,N-1,t_min,X[j],V[j]);
        for(int i=X[j];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];
        //cout<<t_sol[1]<<' ';
	}
	//for(int ans:answer)cout<<ans<<' ';
	return answer;
}
/*int main(){
    vector<int> A={3,2,1,4},X={0,1,2,0},V={3,5,5,5};
    countScans(A,X,V);
}*/

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