oj.uz

Submission #209468

# Submission time Handle Problem Language Result Execution time Memory
209468 2020-03-14T09:57:49 Z TAISA_ Bubble Sort 2 (JOI18_bubblesort2) C++14
17 / 100
 133 ms 1016 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using D=long double;
using P=pair<ll,ll>;
struct BIT{
	vector<int> bit;
	BIT(int n){
		bit.resize(++n);
	}
	void add(int k,int x){
		for(++k;k<bit.size();k+=k&-k){
			bit[k]+=x;
		}
	}
	int get(int k){
		int res=0;
		for(++k;k>0;k-=k&-k){
			res+=bit[k];
		}
		return res;
	}
};
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
	int n=A.size(),q=X.size();
	assert(n<=2000&&q<=2000);
	vector<int> v;
	for(int i=0;i<n;i++){
		v.eb(A[i]);
	}
	for(int i=0;i<q;i++){
		v.eb(V[i]);
	}
	sort(all(v));
	v.erase(unique(all(v)),v.end());
	int m=v.size();
	for(int i=0;i<n;i++){
		A[i]=lower_bound(all(v),A[i])-v.begin();
	}
	vector<int> res(q);
	for(int i=0;i<q;i++){
		V[i]=lower_bound(all(v),V[i])-v.begin();
		A[X[i]]=V[i];
		BIT bit(m+5);
		for(int j=0;j<n;j++){
			res[i]=max(res[i],bit.get(m+1)-bit.get(A[j]));
			bit.add(A[j],1);
		}
	}
	return res;
}

Compilation message

bubblesort2.cpp: In member function 'void BIT::add(int, int)':
bubblesort2.cpp:15:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(++k;k<bit.size();k+=k&-k){
           ~^~~~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 376 KB Output is correct
2 Correct 27 ms 376 KB Output is correct
3 Correct 132 ms 508 KB Output is correct
4 Correct 132 ms 504 KB Output is correct
5 Correct 133 ms 504 KB Output is correct
6 Correct 125 ms 504 KB Output is correct
7 Correct 130 ms 504 KB Output is correct
8 Correct 131 ms 504 KB Output is correct
9 Correct 130 ms 504 KB Output is correct
10 Correct 124 ms 504 KB Output is correct
11 Correct 121 ms 504 KB Output is correct
12 Correct 123 ms 504 KB Output is correct
13 Correct 120 ms 504 KB Output is correct
14 Correct 119 ms 492 KB Output is correct
15 Correct 118 ms 496 KB Output is correct
16 Correct 123 ms 504 KB Output is correct
17 Correct 124 ms 504 KB Output is correct
18 Correct 121 ms 504 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 376 KB Output is correct
2 Correct 27 ms 376 KB Output is correct
3 Correct 132 ms 508 KB Output is correct
4 Correct 132 ms 504 KB Output is correct
5 Correct 133 ms 504 KB Output is correct
6 Correct 125 ms 504 KB Output is correct
7 Correct 130 ms 504 KB Output is correct
8 Correct 131 ms 504 KB Output is correct
9 Correct 130 ms 504 KB Output is correct
10 Correct 124 ms 504 KB Output is correct
11 Correct 121 ms 504 KB Output is correct
12 Correct 123 ms 504 KB Output is correct
13 Correct 120 ms 504 KB Output is correct
14 Correct 119 ms 492 KB Output is correct
15 Correct 118 ms 496 KB Output is correct
16 Correct 123 ms 504 KB Output is correct
17 Correct 124 ms 504 KB Output is correct
18 Correct 121 ms 504 KB Output is correct
19 Runtime error 10 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 376 KB Output is correct
2 Correct 27 ms 376 KB Output is correct
3 Correct 132 ms 508 KB Output is correct
4 Correct 132 ms 504 KB Output is correct
5 Correct 133 ms 504 KB Output is correct
6 Correct 125 ms 504 KB Output is correct
7 Correct 130 ms 504 KB Output is correct
8 Correct 131 ms 504 KB Output is correct
9 Correct 130 ms 504 KB Output is correct
10 Correct 124 ms 504 KB Output is correct
11 Correct 121 ms 504 KB Output is correct
12 Correct 123 ms 504 KB Output is correct
13 Correct 120 ms 504 KB Output is correct
14 Correct 119 ms 492 KB Output is correct
15 Correct 118 ms 496 KB Output is correct
16 Correct 123 ms 504 KB Output is correct
17 Correct 124 ms 504 KB Output is correct
18 Correct 121 ms 504 KB Output is correct
19 Runtime error 10 ms 1016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -