oj.uz

Submission #730904

# Submission time Handle Problem Language Result Execution time Memory
730904 2023-04-26T15:18:48 Z esomer Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 91 ms 5076 KB 
#include<bits/stdc++.h>
#include "bubblesort2.h"
 
using namespace std;
 
#define endl "\n"

typedef long long int ll;
 
const int MOD = 1e9 + 7;

struct segTree{
	vector<int> v;
	vector<int> upd;
	int siz;
	void init(int n){
		siz = 1;
		while(siz < n) siz *= 2;
		v.assign(2 * siz, 0);
		upd.assign(2 * siz, 0);
	}
	
	void set(int l, int r, int u, int x, int lx, int rx){
		if(lx >= l && rx <= r){
			upd[x] += u;
			v[x] += u;
			return;
		}
		if(lx >= r || rx <= l) return;
		int m = (lx + rx) / 2;
		set(l, r, u, 2 * x + 1, lx, m);
		set(l, r, u, 2 * x + 2, m, rx);
		v[x] = max(v[2 * x + 1], v[2 * x + 2]) + upd[x];
	}
	
	void set(int l, int r, int u){
		set(l, r, u, 0, 0, siz);
	}
	
	int get_ans(){
		return v[0];
	}
};

vector<int> countScans(vector<int> A,vector<int> V1,vector<int> V2){
	int n = (int)A.size();
	int q = (int)V1.size();
	vector<int> all(n + q);
	for(int i = 0; i < n; i++) all[i] = A[i];
	for(int i = 0; i < q; i++) all[i + n] = V2[i];
	sort(all.begin(), all.end());
	unordered_map<int, int> m;
	int curr = 0;
	for(int i = 0; i < n + q; i++){
		if(i == 0) {m[all[i]] = curr; curr++;}
		else{
			if(all[i] == all[i-1]) continue;
			m[all[i]] = curr;
			curr++;
		}
	}
	segTree st; st.init(curr);
	vector<set<int>> pos(curr);
	for(int i = 0; i < n; i++){
		pos[m[A[i]]].insert(i);
		st.set(m[A[i]], curr, -1);
	}
	for(int i = 0; i < curr; i++){
		if((int)pos[i].size() > 0){
			st.set(i, i + 1, *pos[i].rbegin());
		}
	}
	vector<int> ans(q);
	for(int qq = 0; qq < q; qq++){
		int i = V1[qq];
		int lst = A[i];
		int nw = V2[qq];
		A[i] = nw;
		lst = m[lst];
		nw = m[nw];
		int lst_pos = *pos[lst].rbegin();
		pos[lst].erase(i);
		if((int)pos[lst].size() > 0) st.set(lst, lst + 1, (*pos[lst].rbegin() - lst_pos));
		st.set(lst, curr, 1);
		if((int)pos[nw].size() == 0){
			pos[nw].insert(i);
			st.set(nw, nw + 1, i);
		}else{
			lst_pos = *pos[nw].rbegin();
			pos[nw].insert(i);
			st.set(nw, nw + 1, (*pos[nw].rbegin() - lst_pos));
		}
		st.set(nw, curr, -1);
		ans[qq] = st.get_ans() + 1;
	}
	return ans;
}

//~ int readInt(){
	//~ int i;
	//~ if(scanf("%d",&i)!=1){
		//~ fprintf(stderr,"Error while reading input\n");
		//~ exit(1);
	//~ }
	//~ return i;
//~ }

//~ int main(){
	//~ int N,Q;
	//~ N=readInt();
	//~ Q=readInt();
	
	//~ std::vector<int> A(N);
	//~ for(int i=0;i<N;i++)
		//~ A[i]=readInt();
	
	//~ std::vector<int> X(Q),V(Q);
	//~ for(int j=0;j<Q;j++){
		//~ X[j]=readInt();
		//~ V[j]=readInt();
	//~ }
	//~ std::vector<int> res=countScans(A,X,V);
	
	//~ for(int j=0;j<int(res.size());j++)
		//~ printf("%d\n",res[j]);
//~ }

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2060 KB Output is correct
2 Correct 54 ms 3512 KB Output is correct
3 Correct 72 ms 4940 KB Output is correct
4 Correct 81 ms 5060 KB Output is correct
5 Correct 81 ms 4944 KB Output is correct
6 Correct 74 ms 5012 KB Output is correct
7 Correct 75 ms 4968 KB Output is correct
8 Correct 91 ms 4932 KB Output is correct
9 Correct 77 ms 5056 KB Output is correct
10 Incorrect 57 ms 5076 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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