oj.uz

Submission #438719

# Submission time Handle Problem Language Result Execution time Memory
438719 2021-06-28T14:23:11 Z CSQ31 Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 8362 ms 1240 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define sz(a) (int)(a.size());
typedef pair<int,int> pii;
vector<int>bit(100000);
int n;
void upd(int pos,int val){
	for(int i=pos;i<=n;i+=i&(-i))bit[i]+=val;
}
int query(int pos){
	int res = 0;
	while(pos){
		res+=bit[pos];
		pos-=pos&(-pos);
	}
	return res;
}
vector<int> countScans(vector<int> a,vector<int> x,vector<int>v){
	int q=sz(x);
	n = sz(a);
	vector<int> answer(q);
	vector<pii>b(n);
	for (int j=0;j<q;j++) {
		for(int i=1;i<=n;i++)bit[i] = 0;
		a[x[j]] = v[j];
		for(int i=0;i<n;i++){b[i].fi = a[i];b[i].se = i+1;}
		sort(b.begin(),b.end());
		int mx = 0;
		for(int i=0;i<n;i++){
			mx = max(query(n)-query(b[i].se),mx);
			upd(b[i].se,1);
		}
		answer[j] = mx;
	}
	return answer;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

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