oj.uz

답안 #601357

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
601357 2022-07-21T18:23:45 Z Iwanttobreakfree Bubble Sort 2 (JOI18_bubblesort2) C++
0 / 100
 9000 ms 1464 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 9091 ms 1464 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 27 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -