oj.uz

Submission #251540

# Submission time Handle Problem Language Result Execution time Memory
251540 2020-07-21T18:45:14 Z test2 Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 8910 ms 936 KB 
#include<bits/stdc++.h>
#include "bubblesort2.h"
 
using namespace std ; 

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

int tree[N * 4] , lazy[N * 4] ; 



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] = max(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 0 ; 
        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 max(s1 , s2) + lazy[node] ; 
}

void add(int ix , int val){

}

void del(int ix , int val){

}

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]] ; 
        }

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


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

	for (int j=0;j<Q;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 ] ; 

                for(int i = 0 ;i < n;i++){  
                        answer[j] = max(answer[j] , i - query(0 , 1 , N , A[i] , A[i] ) ) ; 
                }

	}
	return answer;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 512 KB Output is correct
2 Correct 124 ms 512 KB Output is correct
3 Correct 722 ms 760 KB Output is correct
4 Correct 708 ms 760 KB Output is correct
5 Correct 688 ms 768 KB Output is correct
6 Incorrect 629 ms 764 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 512 KB Output is correct
2 Correct 124 ms 512 KB Output is correct
3 Correct 722 ms 760 KB Output is correct
4 Correct 708 ms 760 KB Output is correct
5 Correct 688 ms 768 KB Output is correct
6 Incorrect 629 ms 764 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 8910 ms 936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 512 KB Output is correct
2 Correct 124 ms 512 KB Output is correct
3 Correct 722 ms 760 KB Output is correct
4 Correct 708 ms 760 KB Output is correct
5 Correct 688 ms 768 KB Output is correct
6 Incorrect 629 ms 764 KB Output isn't correct
7 Halted 0 ms 0 KB -