oj.uz

Submission #209464

# Submission time Handle Problem Language Result Execution time Memory
209464 2020-03-14T09:54:02 Z TAISA_ Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 10 ms 1144 KB 
#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;
	}
};
vector<int> countScans(vector<int> A,vector<int> X,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]));
		}
	}
	return res;
}

Compilation message

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

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 1144 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 Incorrect 10 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -