oj.uz

Submission #70760

# Submission time Handle Problem Language Result Execution time Memory
70760 2018-08-23T10:16:28 Z KLPP Bubble Sort 2 (JOI18_bubblesort2) C++14
38 / 100
 7223 ms 5024 KB 
#include "bubblesort2.h"
#include<vector>
#include<iostream>
#include<algorithm>
#include<set>
using namespace std;
typedef long long int lld;
#define INF 1000000000
class FT{
	int arr[100000];
	int n;
	public:
	void init(int N){
		n=N;
		for(int i=0;i<=n;i++){
			arr[i]=0;
		}
	}
	int query(int prefix){
		prefix++;
		int ans=0;
		for(;prefix>0;prefix-=(prefix&(-prefix))){
			ans+=arr[prefix];
		}return ans;
	}
	void update(int pos){
		pos++;
		for(;pos<=n;pos+=(pos&(-pos))){
			arr[pos]++;
		}
	}
	void print(){
		for(int i=0;i<=n;i++){
			cout<<arr[i]<<" ";
		}cout<<endl;
	}
};
FT *F;
int compute(vector<int> v){
	int n=v.size();
	F->init(n);
	pair<int,int> arr[n];
	for(int i=0;i<n;i++){
		arr[i]=pair<int,int>(v[i],i);
	}sort(arr,arr+n);
	int prev=n-1;
	int ans=0;
	for(int i=n-1;i>-1;i--){
		if(i==0 || arr[i-1]!=arr[i]){
			for(int j=prev;j>=i;j--){
				ans=max(ans,F->query(arr[j].second));
			}
			for(int j=prev;j>=i;j--){
				F->update(arr[j].second);
			}
			prev=i-1;
		}
	}
	return ans;
}
struct node{
	int l,r;
	int val;
	node *left,*right;
};
void build(node *n,int l, int r){
	
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){F=new FT();
	if(A.size()<=8000){
	vector<int> ans;
	for(int i=0;i<X.size();i++){
		A[X[i]]=V[i];
		ans.push_back(compute(A));
	}
	return ans;
	}
	
	set<int> arr[100];
	for(int i=0;i<A.size();i++){
		arr[A[i]-1].insert(i);
		//cout<<A[i]-1<<" "<<i<<endl;
	}
	vector<int> a;
	for(int i=0;i<X.size();i++){
		arr[A[X[i]]-1].erase(X[i]);
		arr[V[i]-1].insert(X[i]);
		A[X[i]]=V[i];
		//cout<<X[i]<<" "<<V[i]<<endl;
		vector<int>H;
		for(int j=0;j<100;j++){
			if(arr[j].size()>0){
				std::set<int>::iterator it2=arr[j].begin();
				
				H.push_back(*it2);
			}
		}
		//for(int j=0;j<H.size();j++)cout<<H[j]<<endl;
		//cout<<compute(H)<<endl;
		a.push_back(compute(H));
	}//cout<<ans.size()<<endl;
	//for(int i=0;i<a.size();i++)cout<<a[i]<<endl;
	return a;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:72:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:80:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<A.size();i++){
              ~^~~~~~~~~
bubblesort2.cpp:85:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<X.size();i++){
              ~^~~~~~~~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 760 KB Output is correct
2 Correct 65 ms 888 KB Output is correct
3 Correct 397 ms 1112 KB Output is correct
4 Correct 418 ms 1228 KB Output is correct
5 Correct 422 ms 1296 KB Output is correct
6 Correct 285 ms 1296 KB Output is correct
7 Correct 344 ms 1400 KB Output is correct
8 Correct 389 ms 1592 KB Output is correct
9 Correct 380 ms 1592 KB Output is correct
10 Correct 251 ms 1592 KB Output is correct
11 Correct 248 ms 1772 KB Output is correct
12 Correct 256 ms 1772 KB Output is correct
13 Correct 269 ms 1792 KB Output is correct
14 Correct 245 ms 1792 KB Output is correct
15 Correct 285 ms 1792 KB Output is correct
16 Correct 249 ms 1932 KB Output is correct
17 Correct 260 ms 1972 KB Output is correct
18 Correct 244 ms 2016 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 760 KB Output is correct
2 Correct 65 ms 888 KB Output is correct
3 Correct 397 ms 1112 KB Output is correct
4 Correct 418 ms 1228 KB Output is correct
5 Correct 422 ms 1296 KB Output is correct
6 Correct 285 ms 1296 KB Output is correct
7 Correct 344 ms 1400 KB Output is correct
8 Correct 389 ms 1592 KB Output is correct
9 Correct 380 ms 1592 KB Output is correct
10 Correct 251 ms 1592 KB Output is correct
11 Correct 248 ms 1772 KB Output is correct
12 Correct 256 ms 1772 KB Output is correct
13 Correct 269 ms 1792 KB Output is correct
14 Correct 245 ms 1792 KB Output is correct
15 Correct 285 ms 1792 KB Output is correct
16 Correct 249 ms 1932 KB Output is correct
17 Correct 260 ms 1972 KB Output is correct
18 Correct 244 ms 2016 KB Output is correct
19 Correct 5494 ms 2400 KB Output is correct
20 Correct 7223 ms 2752 KB Output is correct
21 Correct 6350 ms 2904 KB Output is correct
22 Correct 7118 ms 3116 KB Output is correct
23 Correct 4756 ms 3288 KB Output is correct
24 Correct 4650 ms 3592 KB Output is correct
25 Correct 4583 ms 3664 KB Output is correct
26 Correct 4733 ms 3664 KB Output is correct
27 Correct 4793 ms 3972 KB Output is correct
28 Correct 4525 ms 4008 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 760 KB Output is correct
2 Correct 65 ms 888 KB Output is correct
3 Correct 397 ms 1112 KB Output is correct
4 Correct 418 ms 1228 KB Output is correct
5 Correct 422 ms 1296 KB Output is correct
6 Correct 285 ms 1296 KB Output is correct
7 Correct 344 ms 1400 KB Output is correct
8 Correct 389 ms 1592 KB Output is correct
9 Correct 380 ms 1592 KB Output is correct
10 Correct 251 ms 1592 KB Output is correct
11 Correct 248 ms 1772 KB Output is correct
12 Correct 256 ms 1772 KB Output is correct
13 Correct 269 ms 1792 KB Output is correct
14 Correct 245 ms 1792 KB Output is correct
15 Correct 285 ms 1792 KB Output is correct
16 Correct 249 ms 1932 KB Output is correct
17 Correct 260 ms 1972 KB Output is correct
18 Correct 244 ms 2016 KB Output is correct
19 Correct 5494 ms 2400 KB Output is correct
20 Correct 7223 ms 2752 KB Output is correct
21 Correct 6350 ms 2904 KB Output is correct
22 Correct 7118 ms 3116 KB Output is correct
23 Correct 4756 ms 3288 KB Output is correct
24 Correct 4650 ms 3592 KB Output is correct
25 Correct 4583 ms 3664 KB Output is correct
26 Correct 4733 ms 3664 KB Output is correct
27 Correct 4793 ms 3972 KB Output is correct
28 Correct 4525 ms 4008 KB Output is correct
29 Incorrect 24 ms 5024 KB Output isn't correct
30 Halted 0 ms 0 KB -