oj.uz

답안 #251543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251543 2020-07-21T19:06:58 Z test2 Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 47 ms 25620 KB 
#include<bits/stdc++.h>
#include "bubblesort2.h"
 
using namespace std ; 

const int N = 5e5 + 7 ;  
int n; 

int tree[N * 4] , lazy[N * 4] ; 
multiset<int> ixs[N]; 


void update(int node , int L , int R , int l , int r , int val){
        if(l > R || r < L || l > r)
                return ; 

        if(L>=l && R<=r){
                lazy[node] += val ; 
                return ; 
        }
        int mid = (L + R) >>1  ; 

        update(node*2+1 , L , mid , l , r , val) ; 
        update(node*2+2 , mid+1 , R , l , r, val) ; 
        tree[node] = min(tree[node *2 +1] + lazy[node*2+1] , tree[node*2+2] + lazy[node *2+2] ); 
}

int query(int node , int L , int R , int l , int r ){
        if(l > R || r < L || l > r)
                return 1e8 ; 
        if(L>=l && R<=r)
                return tree[node] + lazy[node]; 
        int mid = (L+R) >> 1 ; 
        int s1 = query(node*2+1 , L , mid , l , r) ; 
        int s2 = query(node*2+2 , mid+1 , R , l , r ) ; 
        return min(s1 , s2) + lazy[node] ; 
}

const int zero = 1e8 ; 
int js[N] ; 

void add(int ix , int val){
        if(ixs[ix].size() == 0){
                update(0 , 1 , N , ix , ix , -zero) ; 
        }        
        ixs[ix].insert(val) ; 
        int mn = *(ixs[ix].begin()) ; 
        update(0 , 1, N , ix , ix , mn - js[ix]) ;
        js[ix] = mn ; 
}

void del(int ix , int val){
        if(ixs[ix].size())
                ixs[ix].erase(ixs[ix].find(val)) ; 

        if(ixs[ix].size() == 0){
                update(0 , 1 , N , ix , ix , zero) ; 
        }
        else{
                int mn = *(ixs[ix].begin()) ; 
                update(0 , 1 , N , ix , ix , mn - js[ix]) ; 
                js[ix] = mn ; 
        }

}

map<int , int > com ; 

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){

	int Q=X.size();
        n = (int) A.size() ; 
	std::vector<int> answer(Q);

        vector<int> aux ; 

        for(auto u : A)
                aux.push_back(u) ; 
        for(auto u : V)
                aux.push_back(u) ; 
        
        sort(aux.begin() , aux.end()) ; 

        int l = 0 , now = 0 ;
        for(int i = 0 ;i < (int) aux.size() ;i++){
                if(aux[i] > l)
                        now ++ ; 
                com[aux[i]] = now ; 
                l = aux[i] ;
        }

        for(int i = 0 ; i < n; i++){
                A[i] = com[A[i]] ; 
                del(A[i] , i) ; 
        }

        for(int i = 0 ;i < Q ;i++){
                V[i] = com[V[i]] ; 
        }


        for(int i = 0 ; i < n; i++){
                add(A[i] , i) ; 
                update( 0 , 1 , N , A[i] +1 , N , 1) ; 
        }

	for (int j=0;j<Q;j++) {
                del(A[X[j]] , X[j]) ; 
                add(V[j] , X[j]) ; 
                if(V[j] >=A[X[j]]){

                        update( 0 , 1 , N , A[X[j]] +1 , V[j] , -1) ;                 
                }
                else{
                        update( 0 , 1 ,N , V[j] +1 , A[X[j]] , 1) ; 
                }
		A[ X[j] ] = V[ j ] ; 

                answer[j] =  query(0 , 1 , N , 1 , N  ) ; 
               

	}
	return answer;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

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